Cod sursa(job #899525)

Utilizator ZanarokStefan Mocanu Zanarok Data 28 februarie 2013 15:01:59
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include <cstdio>
#include <vector>
#include <stack>
#define MAX 1000005
using namespace std;

int n,m,indecs;
vector <vector <int> > C;
vector <int> adj[MAX],con,in_stack,index,lowlink;
stack <int> S;

int minim(int a, int b)
{
    if(a<b)
        return a;
    return b;
}
void tarjan(int a)
{
    index[a]=indecs;
    lowlink[a]=indecs;
    indecs++;
    S.push(a);in_stack[a]=1;
    int b=adj[a].size();
    for(int k=0;k<b;k++)
        if(index[adj[a][k]]==-1)
        {
            tarjan(adj[a][k]);
            lowlink[a]=minim(lowlink[a],lowlink[adj[a][k]]);
        }
        else
            if(in_stack[adj[a][k]])
                lowlink[a]=minim(lowlink[a],lowlink[adj[a][k]]);
    if(index[a]==lowlink[a])
    {
        con.clear();
        int nod;
        do
        {
            nod=S.top();
            con.push_back(nod);
            S.pop();
        }while(nod!=a);
        C.push_back(con);
    }
}

int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    scanf("%d %d",&n,&m);
    int x,y;
    for(int k=1;k<=m;k++)
    {
        scanf("%d %d",&x,&y);
        adj[x-1].push_back(y-1);
    }
    index.resize(n);in_stack.resize(n);lowlink.resize(n);
    in_stack.assign(n,0);index.assign(n,-1);
    for(int k=0;k<=n-1;k++)
        if(index[k]==-1)
            tarjan(k);
    printf("%d\n",x=C.size());
    for(int k=0;k<x;k++)
    {
        y=C[k].size();
        for(int j=0;j<y;j++)
            printf("%d ",C[k][j]+1);
        printf("\n");
    }
}