Cod sursa(job #2214605)

Utilizator alexsandulescuSandulescu Alexandru alexsandulescu Data 19 iunie 2018 14:32:44
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");

int N, M, x, y, k, s, Q[100003], visit[100003];
vector<int> G[100003], GT[100003], sol[100003];

void df(int x) {
    visit[x] = true;
    for(int i = 0; i < G[x].size(); i++)
        if(!visit[G[x][i]]) df(G[x][i]);
    Q[++k] = x;
}

void df_transpus(int x) {
    visit[x] = true;
    for(int i = 0; i < GT[x].size(); i++)
        if(!visit[GT[x][i]])
            df_transpus(GT[x][i]);
    sol[s].push_back(x);
}
int main()
{
    f >> N >> M;
    for(int i = 1; i <= M; i++) {
        f >> x >> y;
        G[x].push_back(y);
        GT[y].push_back(x);
    }
    for(int i = 1; i <= N; i++)
        if(!visit[i])
            df(i);

    for(int i = 1; i <= N; i++)
        visit[i] = false;

    for(int i = N; i >= 1; i--) {
        int x = Q[i];
        if(!visit[x]) {
            s++;
            df_transpus(x);
        }
    }
    g << s << "\n";
    for(int i = 1; i <= s; i++) {
        for(int j = 0; j < sol[i].size(); j++)
            g << sol[i][j] << " ";
        g << "\n";
    }
    return 0;
}