讨论/题目交流/🏆 第 154 场力扣中秋周赛/
🏆 第 154 场力扣中秋周赛

力扣的扣友们中秋快乐🥮,欢迎前来参加本场周赛,小伙伴们可以在这里交流分享参赛心得以及体验。

image.png

展开讨论
力扣 (LeetCode)发起于 2019-09-15
最近编辑于 2019-09-15

第四题这是我写的也能过,我看都用tarjan算法,我这个算法对吗,是不是数据太弱才过的?
class Solution {
public:
vector<int> graph[100001];
int used[100001]={0};
unordered_set<int> ss;
unordered_set<int> cur;
int indegree[100001]={0};

vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
    for(auto c:connections)
    {
        graph[c[0]].push_back(c[1]);
        graph[c[1]].push_back(c[0]);
        indegree[c[0]]++;
        indegree[c[1]]++;
    }
    int i;
    for(i=0;i<n;++i)if(indegree[i]==1)cur.insert(i);
    vector<vector<int>> res;
    while(!cur.empty())
    {
        ss.clear();
        for(auto it=cur.begin();it!=cur.end();++it)
        {
            int t=*it;
            used[t]=1;
            for(auto adj:graph[t])if(!used[adj])
            {
                res.push_back({t,adj});
                indegree[adj]--;
                if(indegree[adj]==1)ss.insert(adj);
            }
        }
        cur=ss;
    }
    return res;
}

};

1
展开全部 10 讨论