Pagini recente » Cod sursa (job #1065006) | Cod sursa (job #172626) | Cod sursa (job #2456150) | Cod sursa (job #2057316) | Cod sursa (job #2785825)
#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;
};
nod noduri[MAXN];
void read_graph(){
int m, i, x, y;
in>>n>>m;
for( i = 0; i < m; i++ ){
in>>x>>y;
noduri[x - 1].next.push_back(y - 1);
noduri[y - 1].next.push_back(x - 1);
}
/*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 = 0; i < n; i++ ){
//cout<<noduri[i].vizitat<<'\n';
if( noduri[i].vizitat == 0 ){
cnt++;
dfs(i);
}
}
out<<cnt;
return 0;
}