Pagini recente » Istoria paginii runda/asdfasdf | Cod sursa (job #766074) | Cod sursa (job #2012954) | Cod sursa (job #2194933) | Cod sursa (job #1909366)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#define N 100001
using namespace std;
vector<int> g[N];
int n;
void citire()
{
int m;
ifstream fin("dfs.in");
fin >> n >> m;
for(int i=1; i<=m; i++)
{
int x,y;
fin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
fin.close();
}
bool visited[N];
void dfs(int src)
{
stack<int> s;
visited[src] = true;
s.push(src);
while(!s.empty())
{
int x = s.top();
s.pop();
vector<int>::iterator i;
for(i = g[x].begin(); i!=g[x].end(); ++i)
if(!visited[*i])
{
visited[*i] = true;
s.push(*i);
}
}
}
void stuff()
{
int count = 0;
int ok;
do
{
ok = 0;
for(int i=1; i<=n; i++)
if(!visited[i])
{
ok = 1;
count++;
dfs(i);
}
}while(ok);
ofstream fout("dfs.out");
fout << count;
fout.close();
}
int main()
{
citire();
stuff();
return 0;
}