Cod sursa(job #2308702)
Utilizator | Data | 27 decembrie 2018 17:06:29 | |
---|---|---|---|
Problema | Parcurgere DFS - componente conexe | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.61 kb |
#include <bits/stdc++.h>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int n,m;
vector<int> adj[100002];
int visited[100002];
int nr=0;
void dfs(int s)
{
visited[s]=1;
for(auto u:adj[s])
{
if(visited[u]==0)
dfs(u);
}
}
int main()
{
fin>>n>>m;
for(int i=0;i<m;i++)
{
int v1,v2;
fin>>v1>>v2;
adj[v1].push_back(v2);
adj[v2].push_back(v1);
}
for(int i=1;i<=n;i++)
if(visited[i]==0)
{
nr++;
dfs(i);
}
fout<<nr;
return 0;
}