Cod sursa(job #1094911)

Utilizator ccristianCristian Chirion ccristian Data 29 ianuarie 2014 23:34:52
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include <fstream>
#include <vector>

using namespace std;
int  k=0, nr_tare_conexe=0;
int vis[100001];
vector <int> ord;
vector <int> rasp[100001];
void dfs(int nod, vector <int> a[], int n){
    vis[nod]=1;
    int i;
    for (i=0; i<a[nod].size(); i++){
        if (vis[a[nod][i]]==0){dfs(a[nod][i], a, n);}
    }
    ord.push_back(nod);

}

void dfs2(int nod, vector <int> a[], int n){
    vis[nod]=1;
    int i;
    for (i=0; i<a[nod].size(); i++){
        if (vis[a[nod][i]]==0){dfs2(a[nod][i], a, n);}
    }
    rasp[nr_tare_conexe].push_back(nod);
}

int main()
{
    ifstream in("ctc.in");
    ofstream out("ctc.out");
    int n, m, e1, e2, i, j;
    in>>n>>m;
    vector <int> a[n+1];
    for (i=1; i<=m; i++){
        in>>e1>>e2;
        a[e2].push_back(e1);
    }
    for (i=1; i<=n; i++){
        vis[i]=0;
    }


    for (i=1; i<=n; i++){
        if(vis[i]==0){dfs(i, a, n);}
    }

    for (i=0; i<=n; i++){
        vis[i]=0;
    }

    for (i=0; i<n; i++){
        if(vis[ord[i]]==0){dfs2(ord[i], a, n); nr_tare_conexe++;}
    }
    out<<nr_tare_conexe<<endl;
    for (i=0; i<nr_tare_conexe; i++){
        for (j=0; j<rasp[i].size(); j++){
            out<<rasp[i][j]<<" ";
        }
        out<<endl;
    }

    return 0;
}