Pagini recente » Cod sursa (job #54993) | Cod sursa (job #1507287) | Cod sursa (job #1752436) | Cod sursa (job #54200) | Cod sursa (job #2785830)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
const int MAXN = 100000;
int n;
struct nod{
vector<int> next;
bool vizitat;
};
vector<nod> noduri;
void read_graph(){
int m, i, x, y;
in>>n>>m;
noduri.resize(n + 1);
for( i = 0; i < m; i++ ){
in>>x>>y;
noduri[x].next.push_back(y);
noduri[y].next.push_back(x);
}
/*for( i = 0; i < n; i++ ){
out<<"numar nod: "<<i + 1<<" ";
for( int j = 0; j < noduri[i].next.size(); j++ )
out<<noduri[i].next[j] + 1<<" ";
out<<'\n';
}*/
}
int dfs(int index){
noduri[index].vizitat = 1;
//cout<<index + 1<<'\n';
for(int i = 0; i < noduri[index].next.size(); i++ ){
//cout<<noduri[noduri[index].next[i]].vizitat<<" "<<noduri[index].next[i] + 1<<" "<<noduri[noduri[index].next[i]].vizitat<<'\n';
if( noduri[noduri[index].next[i]].vizitat == 0){
dfs(noduri[index].next[i]);
}
}
}
int main()
{
int cnt, i;
read_graph();
cnt = 0;
for( i = 1; i <= n; i++ ){
//cout<<noduri[i].vizitat<<'\n';
if( noduri[i].vizitat == 0 ){
cnt++;
dfs(i);
}
}
out<<cnt;
return 0;
}