Cod sursa(job #1787634)

Utilizator pitradaPit-Rada Ionel-Vasile pitrada Data 24 octombrie 2016 20:59:58
Problema Componente tare conexe Scor 12
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include <fstream>
#include <cstring>

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], *C[100002],*p;
int k;
void fillp(int x)
{
    vizp[x]=1;
    for(nod *p=Lp[x];p!=0;p=p->urm)
    {
        if(vizp[p->v]==0)
        {
            fillp(p->v);
        }
    }
}
void fillm(int x)
{
    vizm[x]=1;
    for(nod *p=Lm[x];p!=0;p=p->urm)
    {
        if(vizm[p->v]==0)
        {
            fillm(p->v);
        }
    }
}
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)
        {
            k++;
            fillp(i);
            fillm(i);
            for(j=1;j<=n;j++)
            {
                if(vizm[j]==1 && vizp[j]==1)
                {
                    viz[j]=k;
                    p=new nod;
                    p->v=j;
                    p->urm=C[k];
                    C[k]=p;
                }
				else
				{
					vizm[j]=0;
					vizp[j]=0;
				}
            }
        }
    }
    fout<<k<<'\n';
    for(i=1;i<=k;i++)
    {
        for(p=C[i];p!=0;p=p->urm)
        {
            x=p->v;
            fout<<x<<" ";
        }
        fout<<'\n';
    }
    return 0;
}