Cod sursa(job #841065)

Utilizator FayedStratulat Alexandru Fayed Data 23 decembrie 2012 18:43:33
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <fstream>
#include <vector>
#include <stack>
#include <cstdio>
using namespace std;

 vector <int> V[100005],Con[100005];
 stack  <int> ST;
int nrc,t;
int vizitat[100005], is_stack[100005];
int low[100005], high[100005];

ifstream f("ctc.in");
ofstream g("ctc.out");

void pp(int nod){

int k;
do{
    k = ST.top();
        ST.pop();
            Con[nrc].push_back(k);
                is_stack[k] = 0;
        } while(k!=nod);
nrc++;
}

void tarjan(int nod){

vizitat[nod] = 1;
    is_stack[nod] = 1;
        low[nod] = high[nod] = t;
            ST.push(nod);
                t++;
    for(vector<int>::iterator it = V[nod].begin();it!=V[nod].end();it++){
        if(!vizitat[*it]){
            tarjan(*it);
            low[nod] = min(low[nod],low[*it]);
       }
       else if(is_stack[*it])
           low[nod] = min(low[nod],high[*it]);

}
if(low[nod] == high[nod])
        pp(nod);
}

int main(){

 int n,m,x,y;
f >> n >> m;
    for(int i=1;i<=m;i++){
        f >> x >> y;
        V[x].push_back(y);
    }

    for(int i=1;i<=n;i++)
        if(!vizitat[i])
            tarjan(i);

g << nrc << '\n';

    for(int i=0;i<nrc;i++){
        for(vector<int>::iterator j = Con[i].begin();j!=Con[i].end();j++)
            g << *j << " ";
    g << '\n';
    }

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