Cod sursa(job #511830)

Utilizator andu04Popa Andi andu04 Data 13 decembrie 2010 13:32:32
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.61 kb
#include <stdio.h>
#include <fstream>
#include <algorithm>
#include <stack>
#include <vector>
#define NMAX 100001
using namespace std;

int n,in=1,viz[NMAX],nr;
stack <int> S;
vector < vector <int> > C;
vector <int> c;
struct nod{
    int inf;
    nod *urm;
};
nod *G[NMAX];

struct comp{
    int index,lowlink;
};
comp v[NMAX];

ofstream g("ctc.out");

void add(int x,int y)
{
    nod *aux=new nod;
    aux->inf=y;
    aux->urm=G[x];
    G[x]=aux;
}
void citire()
{
    int m;
    freopen ("ctc.in","r",stdin);
    scanf ("%d%d",&n,&m);
    int x,y;
    for (int i=1;i<=m;i++)
    {
        scanf ("%d%d",&x,&y);
        add(x,y);
    }
}
void tarjan (int t)
{
    v[t].index=in;
    v[t].lowlink=in;
    in++;
    S.push(t);viz[t]=1;
    for (nod *p=G[t];p;p=p->urm)
    {
        if (!v[p->inf].index)
        {
            tarjan(p->inf);
            v[t].lowlink=min(v[t].lowlink,v[p->inf].lowlink);
        }
        else
            if (viz[p->inf])
                v[t].lowlink=min(v[t].lowlink,v[p->inf].index);
    }
    int x;
    if (v[t].index==v[t].lowlink)
    {
        c.clear();
        do{
            x=S.top();
            S.pop();
            c.push_back(x);
            viz[x]=0;
        }while (t!=x);
        C.push_back(c);

    }
}
void afis()
{
    citire();
    for (int i=1;i<=n;i++)
        if (!v[i].index)
            tarjan(i);
    g<<C.size()<<"\n";
    for (int i=0;i<C.size();i++)
    {
        for (int j=0;j<C[i].size();j++)
            g<<C[i][j]<<" ";
        g<<"\n";
    }
}
int main()
{
    afis();
    return 0;
}