Cod sursa(job #2583118)

Utilizator CharacterMeCharacter Me CharacterMe Data 17 martie 2020 19:27:17
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.71 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("drumuri5.in");
ofstream fout("drumuri5.out");

int n, m, sol, cnt, sum, nr, sz, l;
int head[150005], to[150005];
vector<int> graph[150005], newG[150005], nodes, new_node, op[150005];
stack<int> stk;
pair<int, int> p[150005];
bitset<150005> check, done, inS;

void connected(int now);

int main()
{

    fin >> n >> m;
    while(m--){
        int x, y;

        fin >> x >> y;
        graph[x].push_back(y);
    }

    for(int i = 1; i <= n; ++i) head[i] = i;

    for(int i = 1; i <= n; ++i){
        if(!check[i]){
            connected(i);
        }
    }

    for(int i = 1; i <= n; ++i){
        if(i == head[i]) ++cnt;

        for(auto next:graph[i]){
            if(head[i] == head[next]) continue;

            newG[head[i]].push_back(head[next]);
            op[head[next]].push_back(head[i]);
            ++to[head[next]];
        }
    }

    for(int i = 1; i <= n; ++i){
        if(!to[i] && head[i] == i)
            nodes.push_back(i);

        check[i] = false;
    }

    sz = nr = nodes.size();

    while(sz){
        if(nr == 1)
            check[nodes[0]] = true;

        for(int i = 0; i < sz; ++i){
            for(auto next:newG[nodes[i]]){
                --to[next];
                if(!to[next])
                    new_node.push_back(next);
            }
        }

        nr += new_node.size();
        sz = new_node.size();

        for(int i = 0; i < sz; ++i){
            for(auto next:op[new_node[i]]){
                if(!done[next]){
                    done[next] = true;
                    --nr;
                }
            }
        }

        nodes.clear();
        nodes = new_node;
        new_node.clear();

        sz = nodes.size();
    }

    for(int i = 1; i <= n; ++i){
        if(check[head[i]] == true)
            ++sol;
    }

    fout << sol << "\n";

    for(int i = 1; i <= n; ++i){
        if(check[head[i]] == true)
            fout << i << " ";
    }

    return 0;
}

void connected(int now){
    check[now] = true;
    p[now] = {++l, l};
    stk.push(now);
    inS[now] = true;

    for(auto next:graph[now]){
        if(!check[next]){
            connected(next);

            p[now].second = min(p[now].second, p[next].second);
        }
        else if(inS[next]){
            p[now].second = min(p[now].second, p[next].first);
        }
    }

    if(p[now].first == p[now].second){
        while(stk.top() != now){
            head[stk.top()] = now;
            inS[stk.top()] = false;
            stk.pop();
        }

        head[stk.top()] = now;
        inS[stk.top()] = false;
        stk.pop();
    }

}