Cod sursa(job #1453912)

Utilizator MaarcellKurt Godel Maarcell Data 24 iunie 2015 23:54:09
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <iostream>
#include <vector>
#include <cstring>
#include <fstream>
using namespace std;

int N,M,st[100100],K,L; vector<int> graf[100010],tgraf[100010],c[100010]; bool v[100100];

void dfs1(int nod){
    if (v[nod]) return;

    v[nod]=1;
    for (int i=0; i<graf[nod].size(); i++)
        dfs1(graf[nod][i]);
    st[++K]=nod;
}

void dfs2(int nod){
    if (v[nod]) return;

    v[nod]=1;
    for (int i=0; i<tgraf[nod].size(); i++)
        dfs2(tgraf[nod][i]);
    c[L].push_back(nod);
}

int main(){
    ifstream fin("ctc.in");
    ofstream fout("ctc.out");
    fin >> N >> M;

    int i,j,x,y;
    for (i=1; i<=M; i++){
        fin >> x >> y;
        graf[x].push_back(y);
        tgraf[y].push_back(x);
    }

    for (i=1; i<=N; i++)
        if (!v[i])
            dfs1(i);

    memset(v,0,sizeof(v));
    for (i=K; i>0; i--)
        if (!v[st[i]]){
            L++;
            dfs2(st[i]);
        }

    fout << L << "\n";
    for (i=1; i<=L; i++, fout << "\n")
        for (j=0; j<c[i].size(); j++)
            fout << c[i][j] << " ";

    return 0;
}