Cod sursa(job #1365577)

Utilizator firutibogdanFiruti Bogdan-Cristian firutibogdan Data 28 februarie 2015 13:12:45
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.85 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];
void dfs(int x)
{
    nod *p;
    viz1[x]=1;
    for(p=v[x];p!=0;p=p->leg)
    {
        if(viz1[p->x]==0 && viz[q->x]==0)
        {
            dfs(p->x);
        }
    }
}
void adfs(int x)
{
    nodd *q;
    viz2[x]=1;
    for(q=av[x];q!=0;q=q->leg)
    {
        if(viz2[q->x]==0 && 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++;
            dfs(i);
            adfs(i);
            for(j=i;j<=n;j++)
            {
                if(viz1[j]==1 && viz2[j]==1 && viz[j]==0)
                {
                    viz[j]=1;
                    //fout<<j<<" ";
                    p=new nod;
                    p->x=j;
                    p->leg=t[c];
                    t[c]=p;
                }
                else
                {
                    if(viz[j]==0)
                    {
                        viz1[j]=0;
                        viz2[j]=0;
                    }
                }
            }
            //fout<<"\n";
        }
    }
    fout<<c<<"\n";
    for(i=1;i<=c;i++)
    {
        for(p=t[i];p!=0;p=p->leg)
        {
            fout<<p->x<<" ";
        }
        fout<<"\n";
    }
    fin.close();
    fout.close();
    return 0;
}