Pagini recente » Cod sursa (job #504255) | Cod sursa (job #900861) | Cod sursa (job #1219848) | Cod sursa (job #1580534) | Cod sursa (job #2839142)
//#include <fstream>
//#include <vector>
//#include <algorithm>
//
//#define NMAX 10004
//
//using namespace std;
//ifstream cin("componenteconexe.in");
//ofstream cout("componenteconexe.out");
//
//vector <int> a[NMAX];
//
//int n,i,j,x,y,lg,k,val,ii,nr;
//int fr[NMAX],m[104][104],scos[NMAX],cont[NMAX];
//
//int main()
//{
// cin>>n;
// while(cin>>x>>y)
// {
// if(m[x][y]==0)
// {
// a[x].push_back(y);
// a[y].push_back(x);
// m[x][y]=1;
// }
//
// // cout<<a[x][a[x].size()-1]<<' '<<a[y][a[y].size()-1]<<'\n';
// }
// for(i=1; i<=n; i++)
// {
// k=a[i].size()-1;
// sort(a[i].begin(),a[i].end());
// }
//
// k=a[1].size();
// for(i=0; i<k; i++)
// fr[a[1][i]]=1;
//
// fr[1]=1;
//
//
//
// for(nr=1; nr<=n; nr++)
// {
//
// ///pt prima instanta
// k=a[nr].size();
// fr[nr]=1;
// for(i=0; i<k; i++)
// fr[a[nr][i]]=1;
//
//
// for(ii=2; ii<=n; ii++)
// {
// k=a[nr].size();
// for(i=0; i<k; i++)
// {
// val=a[nr][i];
// lg=a[val].size();
// for(j=0; j<lg; j++)
// {
// if(fr[a[val][j]]==0)
// {
// //st[val]=1;
// a[nr].push_back(a[val][j]);
// fr[a[val][j]]=1;
// }
// }
// }
// }
// }
//
//
// for(i=1;i<=n;i++)
// {
// sort(a[i].begin(),a[i].end());
// }
//
// nr=0;
// for(i=1;i<=n;i++)
// {
// if(scos[i]==0)
// {
// nr++;
// m[nr][1]=i;
// cont[nr]=1;
// //cout<<i<<' ';
// k=a[i].size();
// for(j=0;j<k;j++)
// {
// //cout<<a[i][j]<<' ';
// cont[nr]++;
// m[nr][cont[nr]]=a[i][j];
// scos[a[i][j]]=1;
// }
// //cout<<'\n';
// }
// }
// cout<<nr<<'\n';
// for(i=1;i<=nr;i++)
// {
// for(j=1;j<=cont[i];j++)
// {
// cout<<m[i][j]<<' ';
// }
// cout<<'\n';
// }
//
//
//// for(i=1; i<=n; i++)
//// {
//// k=a[i].size();
//// //if(st[i]==0)
//// for(j=0; j<k; j++)
//// cout<<a[i][j]<<' ';
//// cout<<'\n';
//// }
//
//
// return 0;
//}
//
#include <fstream>
#include <vector>
#include <algorithm>
#define NMAX 100004
using namespace std;
ifstream cin("dfs.in");
ofstream cout("dfs.out");
///lista de adiacenta, repr ca vectori din STL
int n,m,start;
///a[x] este un vector din stl care contine lista de adiacenta a lui x
vector <int> a[NMAX];
vector <int> sol[NMAX];
int d[NMAX];
bool viz[NMAX];
void citire();
void dfs(int x,int cont);
int main()
{
citire();
int i,cont=0,j;
for(i=1;i<=n;i++)
{
if(viz[i]==0)
{
cont++;
dfs(i,cont);
// cout<<'\n';
}
}
cout<<cont<<'\n';
// for(i=1;i<=cont;i++)
// {
// sort(sol[i].begin(),sol[i].end());
// }
//
// for(i=1;i<=cont;i++)
// {
// for(j=0;j<sol[i].size();j++)
// cout<<sol[i][j]<<' ';
// cout<<'\n';
// }
return 0;
}
void citire()
{
int i,x,y;
cin>>n>>m;
while(cin>>x>>y)
{
///adaug pe y in lista de adiacenta a lui x si invers
a[x].push_back(y);
a[y].push_back(x);
}
}
void dfs(int x,int cont)
{
int i;
///vizitez varful x
sol[cont].push_back(x);
//cout<<x<<' ';
viz[x]=1;
///parcurg vecinii lui x
for(i=0;i<a[x].size();i++)
{
if(!viz[a[x][i]]) ///vecin i nevizitat
{
dfs(a[x][i],cont);
}
}
}