Cod sursa(job #1895081)

Utilizator pusi23Faier Andreea pusi23 Data 27 februarie 2017 19:32:57
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include<fstream>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
struct nod
{
    int v;
    nod *adr;
};
int n,m,i,j,viz[200002],viz1[200002],viz2[200002],c,x,y;
nod *L1[100001], *L2[100001], *p;
void dfs(nod *L[],int vf, int v[])
{
    int st[100001],k;
    nod *p;
    k=1;
    st[k]=vf;
    v[vf]=1;
    while(k>0)
    {
        for(p=L[st[k]];p!=0;p=p->adr)
        {
            if(v[p->v]==0)
                break;
        }
        if(p==0)
            k--;
        else
        {
            v[p->v]=1;
            k++;
            st[k]=p->v;
        }
    }
}
int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y;
        p=new nod;
        p->v=y;
        p->adr=L1[x];
        L1[x]=p;
        p=new nod;
        p->v=x;
        p->adr=L2[y];
        L2[y]=p;
    }
    c=0;
    for(i=1;i<=n;i++)
    {
        if(viz[i]==0)
        {
            c++;
            dfs(L1,i,viz1);
            dfs(L2,i,viz2);
            for(j=1;j<=n;j++)
            {
                if(viz1[j]==1&&viz2[j]==1) viz[j]=c;
            }
            for(j=1;j<=n;j++)
            {
                viz1[j]=0;
                viz2[j]=0;
            }
        }
    }
    g<<c<<'\n';
    for(i=1;i<=c;i++)
    {
        for(j=1;j<=n;j++)
        {
            if(viz[j]==i) g<<j<<" ";
        }
        g<<'\n';
    }
    f.close();
    g.close();
    return 0;
}