Cod sursa(job #944927)

Utilizator dutzulBodnariuc Dan Alexandru dutzul Data 30 aprilie 2013 00:02:38
Problema Componente tare conexe Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <fstream>
#include <iostream>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");

#define LE 100666
#include <vector>
#define pb push_back

bool viz[LE];
int pos[LE],result[LE];
vector<int> H[LE];
int i,K,n,m,xx,yy,t;
vector<int> res[LE];

void dfs1(int node) {

    viz[node]=true;
    int N=H[node].size();

    for(int i=0; i<N; ++i)
        if (viz[H[node][i]]==false)
            dfs1(H[node][i]);

    pos[++K]=node;
}

void dfs2(int node) {
    viz[node]=true;
    int N=H[node].size();
    result[++K]=node;

    for(int i=0; i<N; ++i)
        if (viz[H[node][i]]==false)
            dfs2(H[node][i]);
}

int main() {
    f>>n>>m;

    for(i=1; i<=m; ++i) {
        f>>xx>>yy;
        H[xx].pb(yy);
    }


    for(i=1; i<=n; ++i)
        if (viz[i]==false)
            dfs1(i);

    for(i=1; i<=n; ++i)
        viz[i]=false;

    for(i=1; i<=n; ++i)
        if(viz[pos[i]]==false) {
            K=0;
            ++t;
            dfs2(pos[i]);

            for(int j=1; j<=K; ++j)
                res[t].pb(result[j]);
        }
    g<<t<<'\n';

    for(i=1;i<=t;++i){
        int N=res[i].size();
        for(int j=0;j<N;++j)
             g<<res[i][j]<<" ";
        g<<'\n';
    }


    f.close();
    g.close();
    return 0;
}