Pagini recente » Cod sursa (job #1534565) | Cod sursa (job #1958811) | Cod sursa (job #824236) | Cod sursa (job #1816666) | Cod sursa (job #1089591)
#include <fstream>
#include <vector>
#include <stack>
#include <string>
using namespace std;
ifstream d("dfs.in");
ofstream o("dfs.out");
void readGraph(int& n, int& m, vector<int> v[100001])
{
int x,y;
d>>n>>m;
for (int i=1;i<=n;i++)
{
d>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
}
int getComp(vector<int> v[100001], int n, int m)
{
stack<int> s;
int a[100001];
int i,k=0,x;
vector<int>::iterator it;
for (i=1;i<=n;i++)
{
if (a[i]==0)
{
k++;
s.push(i);
while (!s.empty())
{
x=s.top();
s.pop();
for (it=v[x].begin();it!=v[x].end();++it)
{
if (a[*it]==0)
{
a[*it]=k;
s.push(*it);
}
}
}
}
}
return k;
}
void returnAnswer(int x)
{
o<<x;
}
int main()
{
vector<int> v[100001];
vector<int>::iterator it;
int n,m;
readGraph(n,m,v);
returnAnswer(getComp(v,n,m));
}