Cod sursa(job #1213775)

Utilizator CostanMiriamCostan Miriam CostanMiriam Data 28 iulie 2014 22:51:05
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

stack <int> s;
vector <int> l[100010],c[100010];

int g,x,y,ctc,i,n,m,j;
int niv[100010],low[100010];

void dfs (int nod) {

   niv[nod]=low[nod]=++g;
   s.push(nod);
   for (int i=0;i<l[nod].size();i++) {
       if (niv[l[nod][i]]==0)
            dfs(l[nod][i]);
        if (niv[l[nod][i]]>0)
            low[nod]=min(low[nod],low[l[nod][i]]);
   }
   if (low[nod]==niv[nod]) {
       ctc++;
       do {
           x=s.top();
           c[ctc].push_back(x);
           s.pop();
           niv[x]*=-1;
       }while (x!=nod);
   }
}

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 (niv[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;
}