Cod sursa(job #649218)

Utilizator bogfodorBogdan Fodor bogfodor Data 15 decembrie 2011 16:57:26
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <cstdio>
#include <stack>
#include <vector>
#include <cstring>
#define Nmax 100005
using namespace std;

FILE *fin=freopen("ctc.in","r",stdin);
FILE *fout=freopen("ctc.out","w",stdout);

int n,m,idx;
int low[Nmax],sir[Nmax];
stack <int> s;
vector < int > adj[Nmax],comp;
vector <vector <int> > C;

int viz[Nmax];
void citire()
{
    scanf("%d %d",&n,&m);
    int x,y;
    for(int i=m;i>0;--i){
        scanf("%d %d",&x,&y);
        adj[x-1].push_back(y-1);
    }
}

void conex(int v)
{
    sir[v]=idx;
    low[v]=idx;
    idx++;
    s.push(v);
    viz[v]=1;
    for(int i=0;i<adj[v].size();i++)
        if(sir[adj[v][i]]==-1){
            conex(adj[v][i]);
            low[v]=min(low[v],low[adj[v][i]]);
        }
        else
            if(viz[adj[v][i]])
            low[v]=min(low[v],low[adj[v][i]]);
    int nod;

    if(low[v]==sir[v]){
    comp.clear();
        do{
            comp.push_back(nod=s.top());
            viz[nod]=0;
            s.pop();
        }while(nod!=v);
    C.push_back(comp);
    }
}

void parcurgere()
{
    memset(sir,-1,sizeof(sir));
    for(int i=0;i<n;i++)
        if(sir[i]==-1)
            conex(i);
}

void afisare()
{
    printf("%d\n",C.size());
    for( int i=0;i<C.size();i++){
        for( int j=0; j<C[i].size();j++)
            printf("%d ",C[i][j]+1);
        printf("\n");
    }
}

int main()
{
    citire();
    parcurgere();
    afisare();
    return 0;
}