Cod sursa(job #1428392)

Utilizator zpaePopescu Andreea zpae Data 4 mai 2015 13:37:28
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include <cstdio>
#include <vector>
#include <stack>
#include <iterator>
#include <algorithm>
using namespace std;
#define MAXN 100005

vector <int> a[MAXN],id(MAXN,-1),lo(MAXN),in(MAXN,0);
vector <int> r[MAXN];
stack <int> s;
int k=0,h=0;

void tarjan(int x)
{
    id[x]=k;
    lo[x]=k;
    k++;
    s.push(x);
    in[x]=1;

    vector <int>::const_iterator it;
    for(it=a[x].begin();it!=a[x].end();++it)
    {
        if(id[*it]==-1)
        {
            tarjan(*it);
            lo[x]=min(lo[x],lo[*it]);
        }
        else if (in[*it])
            lo[x]=min(lo[x],lo[*it]);
    }
    if(id[x]==lo[x])
    {
        int e;
        do{
            e=s.top();
            r[h].push_back(e);
            s.pop();
            in[e]=0;
        }while(e!=x);
        h++;
    }
}

int main ()
{
    int n,m,i,j,x,y;
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=0;i<m;++i)
    {
        scanf("%d%d",&x,&y);
        a[x-1].push_back(y-1);
    }
    for(i=0;i<n;i++)
        if(id[i]==-1)
            tarjan(i);

    printf("%d\n",h);
    for(i=0;i<h;++i)
    {
        for(j=0;j<r[i].size();++j)
            printf("%d ",r[i][j]+1);
        printf("\n");
    }
    return 0;
}