Cod sursa(job #1608442)

Utilizator andytosaAndrei Tosa andytosa Data 22 februarie 2016 08:51:02
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <fstream>
#include <queue>
#include <vector>

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

vector<int> v[100010], t[100010];
int comp[100010], n, m, x, y, viz[100010], st[100010], nr;

void DF(int nod){
    viz[nod] = 1;
    for(int i = 0; i < v[nod].size(); ++i){
        if(viz[v[nod][i]] == 0){
            DF(v[nod][i]);
        }
    }

    st[++st[0]] = nod;
}
void DF2(int nod){
    comp[nod] = nr;
    for(int i = 0; i < t[nod].size(); ++i){
        if(comp[t[nod][i]] == 0){
            DF2(t[nod][i]);
        }
    }
}
int main()
{
    fin >> n >> m;
    for(int i = 1; i <= m; ++i){
        fin >> x >> y;
        v[x].push_back(y);
        t[y].push_back(x);
    }
    for(int i = 1; i <= n; ++i){
        if(viz[i] == 0)
            DF(i);
    }
    while(st[0]){
        if(comp[st[st[0]]] == 0){
            nr++;
            DF2(st[st[0]--]);
        }
        else {
            st[0]--;
        }
    }
    fout << nr << '\n';
    for(int i = 1; i <= nr; ++i){
        for(int j = 1; j <= n; ++j)
            if(comp[j] == i)
                fout << j << ' ';
        fout << '\n';
    }

    return 0;
}