Cod sursa(job #1808132)

Utilizator sotoc1999Sotoc George sotoc1999 Data 17 noiembrie 2016 13:18:33
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int n,m;
struct nod{
    int val;
    struct nod *urm;
}*L[100004],*l[100004],*actual;
bool viz[100003];
int st[100003];
int vf;
int nr;
void dfs(int k)
{
    struct nod *act;
    act=L[k];
    viz[k]=true;
    while(act!=NULL)
    {
        if(viz[act->val]==false)
            dfs(act->val);
        act=act->urm;
    }
    vf++;
    st[vf]=k;
}
void dfs1(int k,int ok)
{
    struct nod *act;
    if(ok==1)
    {
        g<<k<<" ";
    }
    act=l[k];
    viz[k]=1;
    while(act!=NULL)
    {
        if(viz[act->val]==0)
            dfs1(act->val,ok);
        act=act->urm;
    }
}
int main()
{
    f>>n>>m;
    int i;
    int x,y;
    for(i=1;i<=m;i++)
    {
        f>>x>>y;
        actual=new nod;
        actual->val=y;
        actual->urm=L[x];
        L[x]=actual;

        actual=new nod;
        actual->val=x;
        actual->urm=l[y];
        l[y]=actual;
    }
    dfs(1);
    nr=1;
    for(i=1;i<=n;i++)
        viz[i]=0;
    bool ok=false;
    int nr=0;
    int aux=vf;
    while(vf>0)
    {
        if(viz[st[vf]]==0){
            dfs1(st[vf],ok);
            nr++;
        }
        vf--;
    }
    g<<nr<<"\n";
    ok=1;
    for(i=1;i<=n;i++)
        viz[i]=0;
    while(aux>0)
    {
        if(viz[st[aux]]==0){
            dfs1(st[aux],ok);
            g<<"\n";
        }
        aux--;
    }
    return 0;
}