Pagini recente » Cod sursa (job #510435) | Cod sursa (job #329408) | Rezultatele filtrării | Cod sursa (job #2327275) | Cod sursa (job #2170175)
#include <bits/stdc++.h>
#define Nmax 100001
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
list <int> G[Nmax];
bool viz[Nmax];
int N;
stack <int> st;
void DFS(int x)
{
st.push(x);
while(!st.empty())
{
x=st.top();
viz[x]=true;
while(!G[x].empty() and viz[G[x].front()]) G[x].pop_front();
if(!G[x].empty())
{
st.push(G[x].front());
G[x].pop_front();
}
else st.pop();
}
}
int main()
{
int n,i,j,m,k;
f>>n>>m;
for(k=0;k<m;k++)
{
f>>i>>j;
G[i].push_back(j);
G[j].push_back(i);
}
for(i=1;i<=n;i++)
if(!viz[i])
{
++N;
DFS(i);
}
g<<N;
return 0;
}