Cod sursa(job #1365583)

Utilizator firutibogdanFiruti Bogdan-Cristian firutibogdan Data 28 februarie 2015 13:23:22
Problema Componente tare conexe Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include<fstream>
using namespace std;
int n,m,i,viz1[100002],viz2[100002],c,viz[100002],x,y,j;
struct nodd
{
    int x;
    nodd *leg;
};
nodd *q,*av[100002];
struct nod
{
    int x;
    nod *leg;
};
nod *p,*v[100002],*t[100002],*z;
int w;
void dfs(int x)
{
    nod *p;
    viz1[x]=w;
    for(p=v[x];p!=0;p=p->leg)
    {
        if(viz1[p->x]<w && viz[q->x]==0)
        {
            dfs(p->x);
        }
    }
}
void adfs(int x)
{
    nodd *q;
    nod *z;
    viz2[x]=w;
    if(viz1[x]==w)
    {
        viz[x]=1;
        z=new nod;
        z->x=x;
        z->leg=t[c];
        t[c]=z;
    }
    for(q=av[x];q!=0;q=q->leg)
    {
        if(viz2[q->x]<w && viz[q->x]==0)
        {
            adfs(q->x);
        }
    }
}
int main()
{
     ifstream fin("ctc.in");
    ofstream fout("ctc.out");
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y;

        p=new nod;
        p->x=y;
        p->leg=v[x];
        v[x]=p;

        q=new nodd;
        q->x=x;
        q->leg=av[y];
        av[y]=q;
    }
    c=0;
    for(i=1;i<=n;i++)
    {
        if(viz[i]==0)
        {
            c++;
            w++;
            dfs(i);
            adfs(i);
        }
    }
    fout<<c<<"\n";
    for(i=1;i<=c;i++)
    {
        for(z=t[i];z!=0;z=z->leg)
        {
            fout<<z->x<<" ";
        }
        fout<<"\n";
    }
    fin.close();
    fout.close();
    return 0;
}