Cod sursa(job #2115605)

Utilizator sotoc1999Sotoc George sotoc1999 Data 26 ianuarie 2018 22:13:37
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.84 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int n,m;
struct nod{
    int vecin;
    struct nod *urm;
}*L[100003],*l[100003],*actual;
int st[100004];
int vf;
int viz[100004];
void dfs(int k,int nr,bool ok)
{
    if(nr==1)
    {
        struct nod *t;
        viz[k]=1;
        for(t=l[k];t!=NULL;t=t->urm)
        {
            if(viz[t->vecin]==0)
                dfs(t->vecin,nr,ok);
        }
        vf++;
        st[vf]=k;
    }
    else
    {
        if(ok)
            g<<k<<" ";
        struct nod *t;
        viz[k]=1;
        for(t=L[k];t!=NULL;t=t->urm)
        {
            if(viz[t->vecin]==0)
                dfs(t->vecin,nr,ok);
        }
    }
}
int main()
{
    int x,y;
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        f>>x>>y;
        actual=new nod;
        actual->vecin=y;
        actual->urm=l[x];
        l[x]=actual;

        actual=new nod;
        actual->vecin=x;
        actual->urm=L[y];
        L[y]=actual;
    }
    int nr=1;
    bool ok=false;
    vf=0;
    //parcurgere in latime pentru a determina nodurile vizitate in ordinea lor de vizitare
    for(int i=1;i<=n;i++)
        if(viz[i]==0)
            dfs(1,nr,ok);
    //reinit viz
    for(int i=1;i<=n;i++)
        viz[i]=0;
    //luam elem din stiva si parcurgem pe graful transpus
    int nrctc=0;
    nr=2;//parcurgerea pe mat transpusa
    int aux=vf;
    while(aux>0)
    {
        if(viz[st[aux]]==0)
        {
            dfs(st[aux],nr,ok);
            nrctc++;
        }
        aux--;
    }
    g<<nrctc<<"\n";
    for(int i=1;i<=n;i++)
        viz[i]=0;
    ok=true;
    while(vf>0)
    {
        if(viz[st[vf]]==0)
        {
            dfs(st[vf],nr,ok);
            g<<"\n";
        }
        vf--;
    }
    return 0;
}