Cod sursa(job #2581005)

Utilizator CharacterMeCharacter Me CharacterMe Data 14 martie 2020 13:53:29
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.42 kb
#include <bits/stdc++.h>

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

int n, m, sol, cnt, sum, nr;
int head[100005];
vector<int> graph[100005], newG[100005];
stack<int> stk;
bitset<100005> check, inS;

void eliminate_cycles(int now);
int find_head(int node);

void dfs(int now, int where);

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]){
            eliminate_cycles(i);
        }
    }
    /*
    for(int i = 1; i <= n; ++i){
        if(head[head[i]] != i) find_head(i);
        if(i == head[i]) ++cnt;

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

    for(int i = 1; i <= n; ++i){
        sort(newG[i].begin(), newG[i].end());
        int sz = newG[i].size();

        for(int j = 0; j < sz; ++j){

            if(j == sz - 1 || newG[i][j] != newG[i][j + 1]){
                solve[i][0].push_back(newG[i][j]);
                solve[newG[i][j]][1].push_back(i);
                ++to[i][1];
                ++to[newG[i][j]][0];
            }
        }
    }
    */

    for(int i = 1; i <= n; ++i) {
        head[i] = find_head(i);
        newG[head[i]].push_back(i);
        if(i == head[i]) ++sol;
    }

    fout << sol << "\n";

    for(int i = 1; i <= n; ++i){
        if(newG[i].size()){
            for(auto node:newG[i]) fout << node << " ";
            fout << "\n";
        }
    }
    return 0;
}

void eliminate_cycles(int now){

    check[now] = inS[now] = true;
    stk.push(now);

    for(auto next:graph[now]){
        int head1 = find_head(now), head2 = find_head(next);

        if(head1 == head2) continue;

        if(check[head2] && inS[head2]){
            while(stk.top() != head2){
                head[stk.top()] = head2;
                stk.pop();
            }
        }
        else if(!check[head2]) eliminate_cycles(next);
    }

    inS[now] = false;

    if(stk.top() == now) stk.pop();

}

int find_head(int node){
    int cpy = node;

    while(head[node] != node) node = head[node];
    while(head[cpy] != cpy){
        int next = head[cpy];
        head[cpy] = node;
        cpy = next;
    }

    return node;
}