Cod sursa(job #1188236)

Utilizator OnimushaLordTiberiu Copaciu OnimushaLord Data 19 mai 2014 09:57:22
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
# include <cstdio>
# define N 100010
# define M 200010

using namespace std;
bool sel[N];

struct point
{
    int inf;
    point *leg;
}*G[M];

point *p,*q;
int i,n,m,nod,nr,x,y;

void load()
{
    int i;
    scanf("%d %d\n", &n, &m);
    for(i=1; i<=n; ++i) G[i]=NULL;
    for(i=1; i<=m; ++i)
    {
        scanf("%d %d\n", &x, &y);
        p=new point;
        q=new point;
        p->inf=y; q->inf=x;
        p->leg=G[x]; q->leg=G[y];
        G[x]=p; G[y]=q;
    }
}
void df(int nod)
{
    int i;
    point *p;
    sel[nod]=true;
    for(p=G[nod]; p; p=p->leg)
         if(!sel[p->inf]) df(p->inf);
}
int main()
{
    freopen("dfs.in", "r", stdin);
    freopen("dfs.out", "w", stdout);
    load();
    for(i=1; i<=n; ++i)
    if(!sel[i])
    {
        df(i);
        nr++;
    }
    printf("%d\n", nr);
}