Pagini recente » Cod sursa (job #34090) | Cod sursa (job #2672560)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <list>
using namespace std;
void dfs(int start,int n,vector<bool>&ell, vector<list<int> >&adj)
{
stack<int>st;
st.push(start);
ell[start]=true;
while(!st.empty()){
int v=st.top();
bool van=false;
for(;!adj[v].empty() && !van;adj[v].pop_front()){
int sz=adj[v].front();
if(!(ell[sz]))
{
ell[sz]=true;
st.push(sz);
van=true;
}
}
if(!van)
st.pop();
}
}
int main()
{
ifstream be("dfs.in");
ofstream ki("dfs.out");
int n,m;
be>>n>>m;
vector<list<int> >adj(n+1);
for(int i=1;i<=m;i++)
{
int x,y;
be>>x>>y;
adj[x].push_back(y);
adj[y].push_back(x);
}
vector<bool>ell(n+1,false);
int db=0;
for(int i=1;i<=n;i++)
if(ell[i]==false)
{
db++;
dfs(i,n,ell,adj);
}
ki<<db;
return 0;
}