Pagini recente » Cod sursa (job #240862) | Cod sursa (job #2668810) | Cod sursa (job #3269655) | Cod sursa (job #1928228) | Cod sursa (job #1107806)
#include <fstream>
#include <vector>
using namespace std;
vector <pair<int,int> > g[100005];
int m,n;
bool check[100005]={0};
void read()
{
ifstream d("dfs.in");
d>>n>>m;
int x,y;
for (int i=1;i<=m;i++)
{
d>>x>>y;
g[x].push_back(make_pair(x,y));
g[y].push_back(make_pair(y,x));
}
}
void dfs(int v)
{
check[v]=1;
vector <pair<int,int> >::iterator iv;
for (iv=g[v].begin(); iv!=g[v].end(); iv++)
{
if (!check[(*iv).second]) dfs((*iv).second);
}
}
int getNrCompCon()
{
int k=0;
for (int i=1;i<=n;i++)
{
if (!check[i])
{
dfs(i);
k++;
}
}
return k;
}
void write()
{
ofstream o("dfs.out");
o<<getNrCompCon();
}
int main()
{
read();
write();
}