Cod sursa(job #1232311)

Utilizator vlady1997Vlad Bucur vlady1997 Data 22 septembrie 2014 17:33:38
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
        #include <cstdio>
        #include <vector>
        #define pb push_back
        using namespace std;
        vector <int> g[100001];
        int nr[100001], n, m;
        bool sel[100001];
        void dfs (int x)
        {
            int i;
            sel[x]=true;
            while (!g[x].empty())
            {
                if (sel[g[x].back()]==false)
                {
                    dfs(g[x].back());
                }
                else
                {
                    g[x].pop_back();
                }
            }
        }
        int main()
        {
            int x, y, i, nrsol=0;
            freopen("dfs.in","r",stdin);
            freopen("dfs.out","w",stdout);
            scanf("%d%d",&n,&m);
            for (i=1; i<=m; i++)
            {
                scanf("%d%d",&x,&y);
                g[x].pb(y);
                g[y].pb(x);
                nr[x]++;
                nr[y]++;
            }
            for (i=1; i<=n; i++)
            {
                if (sel[i]==false)
                {
                    dfs(i);
                    nrsol++;
                }
            }
            printf("%d",nrsol);
            fclose(stdin);
            fclose(stdout);
            return 0;
        }