Cod sursa(job #1808127)

Utilizator sotoc1999Sotoc George sotoc1999 Data 17 noiembrie 2016 13:08:20
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 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;
int 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 valoare)
{
    struct nod *act;
    act=l[k];
    viz[k]=valoare;
    while(act!=NULL)
    {
        if(viz[act->val]==0)
            dfs1(act->val,valoare);
        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;
    while(vf>0)
    {
        if(viz[st[vf]]==0){
            dfs1(st[vf],nr);
            nr++;
        }
        vf--;
    }
    nr--;
    g<<nr<<"\n";
    int j;
    for(i=1;i<=nr;i++)
    {
        for(j=1;j<=n;j++)
        {
            if(viz[j]==i)
                g<<j<<" ";
        }
        g<<"\n";
    }
    return 0;
}