Cod sursa(job #1099532)

Utilizator ccristianCristian Chirion ccristian Data 5 februarie 2014 22:04:28
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
int use[100001], st[100001], scos[100001];
int stc=0, nrtc=0;
vector <int> sol[100001];

void dfs(int nod, vector <int> a[]){
    use[nod]=1;
    st[stc]=nod; stc++;
    int i;
    for (i=0; i<a[nod].size(); i++){
        if (!use[a[nod][i]] && !scos[a[nod][i]]){dfs(a[nod][i], a);}
    }
}

void dfs1(int nod, vector <int> t[]){
    use[nod]=1;
    int i;
    for (i=0; i<stc; i++){
        if (nod==st[i]){sol[nrtc].push_back(nod); scos[nod]=1;}
    }
    for (i=0; i<t[nod].size(); i++){
        if (!use[t[nod][i]] && !scos[t[nod][i]]){dfs1(t[nod][i], t);}
    }
}

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

    for (i=1; i<=n; i++){
        if (!scos[i]){dfs(i, a);}
        for (j=1; j<=n; j++){
        use[j]=0;
        }
        if (!scos[i]){dfs1(i, t); nrtc++;}
        stc=0;
    }

    out<<nrtc;
    for (i=0; i<nrtc; i++){
        out<<endl;
        for (j=0; j<sol[i].size(); j++){
            out<<sol[i][j]<<" ";
        }
    }
    return 0;
}