Cod sursa(job #1782129)

Utilizator gamanedyGaman Eduard-Marian gamanedy Data 17 octombrie 2016 20:03:41
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.51 kb
#include <fstream>

using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n,m,viz[100002],vizp[100002],vizm[100002];
struct nod
{
    int v;
    nod *urm;
};
nod *Lp[100002], *Lm[100002], *p;
int z[100002],k;
void fillp(int x)
{
    vizp[x]=1;
    for(nod *p=Lp[x];p!=0;p=p->urm)
    {
        int y=p->v;
        if(vizp[y]==0)
        {
            fillp(y);
        }
    }
}
void fillm(int x)
{
    vizm[x]=1;
    for(nod *p=Lm[x];p!=0;p=p->urm)
    {
        int y=p->v;
        if(vizm[y]==0)
        {
            fillm(y);
        }
    }
}
int i,j,x,y,c;

int main()
{
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y;
        p=new nod;
        p->v=y;
        p->urm=Lp[x];
        Lp[x]=p;
        p=new nod;
        p->v=x;
        p->urm=Lm[y];
        Lm[y]=p;
    }
    k=0;
    for(i=1;i<=n;i++)
    {
        if(viz[i]==0)
        {
            for(j=1;j<=n;j++)
            {
                vizm[j]=0;
                vizp[j]=0;
            }
            k++;
            fillp(i);
            fillm(i);
            for(j=1;j<=n;j++)
            {
                if(vizm[j]==1 && vizp[j]==1)
                {
                    viz[j]=k;
                }
            }
        }
    }
    fout<<k<<'\n';
    for(i=1;i<=k;i++)
    {
        for(j=1;j<=n;j++)
        {
            if(viz[j]==i)
            {
                fout<<j<<" ";
            }
        }
        fout<<'\n';
    }
    return 0;
}