Cod sursa(job #1438189)
Utilizator | Data | 19 mai 2015 11:22:55 | |
---|---|---|---|
Problema | Parcurgere DFS - componente conexe | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.67 kb |
#include <fstream>
#include <vector>
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
const int NMAX=100010;
int n,m,j,contor,a,b;
int marcat[NMAX];
vector<int> g[NMAX];
void dfs(int x)
{
marcat[x]=1;
for(int i=0;i<g[x].size();i++)
{
if(marcat[g[x][i]]==0) dfs(g[x][i]);
}
}
int main()
{
in>>n>>m;
for(j=1;j<=m;j++)
{
in>>a>>b;
g[a].push_back(b);
g[b].push_back(a);
}
for(j=1;j<=n;j++)
{
if(marcat[j]==0)
{
dfs(j);
contor++;
}
}
out<<contor;
in.close();
out.close();
return 0;
}