Cod sursa(job #899230)

Utilizator unsilviuContvechidontdeactivatepls unsilviu Data 28 februarie 2013 13:27:24
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <fstream>
#include <vector>
using namespace std;

vector <int> v[100001];
vector <int> vt[100001];
vector <int> ct[100001];

int vz[100001];
int n,m,nr;


vector <int> nodes;

void dfs(int x) {
    int i;
    vz[x]=1;
    for (i=0; i<v[x].size(); i++)
        if (!vz[v[x][i]])
            dfs(v[x][i]);

    nodes.push_back(x);
}

void tfs(int x) {
    int i;
    vz[x]=0;
    for (i=0; i<vt[x].size(); i++)
        if (vz[vt[x][i]])
            tfs(vt[x][i]);

    ct[nr].push_back(x);
}

int main() {
    int i,a,b,j;
    ifstream in("ctc.in");
    ofstream out("ctc.out");
    in>>n>>m;
    for (i=1; i<=m; i++) {
        in>>a>>b;
        v[a].push_back(b);
        vt[b].push_back(a);
    }

    for (i=1; i<=n; i++)
        if (!vz[i])
            dfs(i);

    for (i=n-1; i>=0; i--)
        if (vz[nodes[i]]) {
            tfs(nodes[i]);
            nr++;
        }

    out<<nr<<'\n';
    for (i=0; i<nr; i++) {
        for (j=0; j<ct[i].size(); j++)
            out<<ct[i][j]<<' ';
        out<<'\n';
    }
    out.close();
    return 0;
}