Pagini recente » Cod sursa (job #830623) | tema | Cod sursa (job #1194899) | Cod sursa (job #2971112) | Cod sursa (job #2321093)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#define DIM 100002
using namespace std;
int pas[DIM];
vector<int> adj[DIM];
int n,m,s;
void dfs(int s)
{
stack<int> st;
st.push(s);
pas[s]=0;
while(!st.empty()) {
int u=st.top();
st.pop();
for(int i=0;i<adj[u].size();i++) {
int v=adj[u][i];
if(pas[v]<0)
pas[v]=pas[u]+1,st.push(v);
}
}
}
int main()
{
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int i, j;
int u, v;
fin>>n>>m;
for(int i=1;i<=n;i++)
pas[i]=-1;
for (i=1; i<=m; i++)
{
fin>>u>>v;
adj[u].push_back(v);
adj[v].push_back(u);
}
int comp=0;
for(int i=1;i<=n;i++) {
if(pas[i]<0)
dfs(i),comp++;
}
fout<<comp;
return 0;
}