Pagini recente » Cod sursa (job #2089033) | Cod sursa (job #51851) | Cod sursa (job #2519459) | Cod sursa (job #2640620) | Cod sursa (job #2465277)
#include<bits/stdc++.h>
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
vector<int> arc[100000];
int n,m;
bool passed[100000];
void read()
{
in>>n>>m;
int a,b;
for(int i=0; i<m; i++)
{
in>>a>>b;
arc[a-1].push_back(b-1);
arc[b-1].push_back(a-1);
}
}
void dfs(int nod)//numarul de noduri dintr-o componenta
{
passed[nod]=true;
for(int k=0; k<arc[nod].size(); k++)
{
int vec=arc[nod][k];
if(!passed[vec])
{
dfs(vec);
}
}
}
int rezolva()
{
int rezultat=0;
for(int i=0; i<n; i++)
{
if(!passed[i])//gasim o componenta conexa
{
dfs(i);
rezultat++;
}
}
return rezultat;
}
int main()
{
read();
out<<rezolva();
return 0;
}