Cod sursa(job #1188667)

Utilizator vlady1997Vlad Bucur vlady1997 Data 20 mai 2014 10:20:40
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
        #include <cstdio>
        using namespace std;
        struct point
        {
            int inf;
            point *leg;
        }*g[200001];
        bool sel[200001];
        void dfs (int i)
        {
            point *p; sel[i]=true;
            for (p=g[i]; p!=NULL; p=p->leg)
            {
                if (sel[p->inf]==false) dfs(p->inf);
            }
        }
        int main()
        {
            int n, m, i, x, y, nr=0;
            point *p, *r;
            freopen("dfs.in","r",stdin);
            freopen("dfs.out","w",stdout);
            scanf("%d%d",&m,&n);
            for (i=1; i<=m; i++) g[i]=NULL;
            for (i=1; i<=n; i++)
            {
                scanf("%d%d",&x,&y);
                p=new point; r=new point;
                p->inf=y; r->inf=x;
                p->leg=g[x]; r->leg=g[y];
                g[x]=p; g[y]=r;
            }
            for (i=1; i<=m; i++)
            {
                if (sel[i]==false)
                {
                    dfs(i);
                    nr++;
                }
            }
            printf("%d",nr);
            fclose(stdin);
            fclose(stdout);
            return 0;
        }