Pagini recente » Cod sursa (job #868984) | Cod sursa (job #2741624) | Cod sursa (job #2331216) | Cod sursa (job #2200003) | Cod sursa (job #2667412)
#include <bits/stdc++.h>
using namespace std;
ifstream fcin("dfs.in");
ofstream fcout("dfs.out");
vector<int>nod[100003];
int n,m,x,y,nrconexe;
bool ap[110];
void dfs(int k)
{
if(ap[k])
return;
ap[k]=1;
for(int i=0;i<nod[k].size();i++)
dfs(nod[k][i]);
}
int main()
{
fcin>>n>>m;
for(int i=1;i<=m;i++){
fcin>>x>>y;
nod[x].push_back(y);
nod[y].push_back(x);
}
int complet=0,start;
while(complet==0){
complet=1;
for(int i=1;i<=n;i++)
if(ap[i]==0){
start=i;
complet=0;
break;
}
if(complet==0){
dfs(start);
nrconexe++;
}
}
fcout<<nrconexe;
return 0;
}
//vector<int>nod[110];
//queue<int>coada;
//int n,m,x;
//bool ap[110];
//
//void gol_ap()
//{
// for(int i=0;i<=110;i++)
// ap[i]=0;
// cout<<endl;
//}
//
//void afisqueue()
//{
// queue<int>af;
// af=coada;
// cout<<'c'<<'-';
// while(!af.empty()){
// cout<<af.front()<<' ';
// af.pop();
// }
// cout<<endl;
//}
//
//void DFS(int k)
//{
// if(ap[k])
// return;
// cout<<k<<' ';
// ap[k]=1;
// for(int i=0;i<nod[k].size();i++)
// DFS(nod[k][i]);
//}
//
//void BFS(int a)
//{
// if(a==0)
// return;
// int b=0,c;
// //cout<<endl<<"nrel-"<<a<<endl;
// for(int i=1;i<=a;i++){
// c=coada.front();
// if(!ap[c]){
// ap[c]=1;
// cout<<c<<' ';
// for(int j=0;j<nod[c].size();j++){
// if(!ap[nod[c][j]]){
// coada.push(nod[c][j]);
// b++;
// }
// }
// }
// coada.pop();
// }
// BFS(b);
//}
//
//int main()
//{
// fcin>>n>>m>>x;
// int a,b;
// for(int i=1;i<=m;i++){
// fcin>>a>>b;
// nod[a].push_back(b);
// nod[b].push_back(a); //graf neorientat
// }
//
// for(int i=1;i<=n;i++)
// sort(nod[i].begin(),nod[i].end());
//
// DFS(x);
// gol_ap();
// coada.push(x);
// BFS(1);
// return 0;
//}
// for(int i=1;i<=n;i++)
// cout<<i<<": "<<nod[i].size()<<endl;
// for(int i=1;i<=n;i++){
// cout<<i<<": ";
// for(int j=0;j<nod[i].size();j++)
// cout<<nod[i][j]<<' ';
// cout<<endl;
// }