Cod sursa(job #1172942)

Utilizator CostanMiriamCostan Miriam CostanMiriam Data 18 aprilie 2014 12:39:16
Problema Componente tare conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream fin ("ctc.in");
ofstream fout ("ctc.out");

int ctc,k,p,i,j,x,y,n,m;

int s[100010],viz[100010],low[100010];

vector <int> C[100010];
vector <int> l[100010];

int minim (int a, int b) {
    if (a<b)
        return a;
    return b;
}

void dfs(int nod) {

    viz[nod]=++k;
    low [nod]=k;
    s[++p]=nod;

    for (int i=0;i<l[nod].size();i++) {
        if (viz[l[nod][i]]==0)
            dfs (l[nod][i]);
        if (viz[l[nod][i]]>0)
            low[nod]=minim(low[nod],low[l[nod][i]]);
    }
    if (low[nod]==viz[nod]){
        ctc++;
        while (s[p]!=nod){
            C[ctc].push_back(s[p]);
            p--;
        }
        C[ctc].push_back(nod);
        p--;
    }
}


int main () {

    fin>>n>>m;
    for (i=1;i<=m;i++) {
        fin>>x>>y;
        l[x].push_back(y);
    }

    for (i=1;i<=n;i++)
        if (viz[i]==0)
            dfs(i);

    fout<<ctc<<"\n";
    for (i=1;i<=ctc;i++) {
        for (j=0;j<C[i].size();j++) {
            fout<<C[i][j]<<" ";
        }
        fout<<"\n";
    }


    return 0;
}