Cod sursa(job #1438190)

Utilizator MrTudorTudor Savulescu MrTudor Data 19 mai 2015 11:26:39
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.59 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
const int n_max=100001;
int n,p,i,a,b,x,c=0;
vector <int> G[n_max];
int marcat[n_max];
void dfs(int x)
{marcat[x]=1;
    for(vector<int>::iterator it=G[x].begin();it!=G[x].end();it++)
    {if(marcat[*it]==0)
    dfs(*it);

    }

}
int main()
{in>>n>>p;
    for(i=1;i<=p;i++)
    {in>>a>>b;
    G[a].push_back(b);
        G[b].push_back(a);
    }
      for(i=1;i<=n;i++)
       if(!marcat[i])
     {dfs(i);
       c++;
       }
       out<<c<<'\n';
    return 0;
}