Pagini recente » Cod sursa (job #1645382) | Cod sursa (job #217189) | Cod sursa (job #1982809) | Cod sursa (job #92246) | Cod sursa (job #632925)
Cod sursa(job #632925)
#include <cstdio>
#include <vector>
#include <stack>
using namespace std;
#define DIM 100005
vector <int> g[DIM];
stack <int> st;
int start[DIM];
bool viz[DIM];
int N,M,cnt;
void read ()
{
scanf ("%d%d",&N,&M);
for (int i=1; i<=M; ++i)
{
int x,y;
scanf ("%d%d",&x,&y);
g[x].push_back (y);
g[y].push_back (x);
}
}
void df (int nod)
{
st.push (nod); viz[nod]=1;
while (!st.empty ())
{
int nod=st.top (),i;
for (i=0; i<g[nod].size (); ++i)
{
int vec=g[nod][i];
if (!viz[vec])
{
viz[vec]=1;
++start[nod];
st.push (vec);
break ;
}
}
if (i==g[nod].size ())
st.pop ();
}
}
void solve ()
{
for (int i=1; i<=N; ++i)
if (!viz[i])
{
++cnt;
df (i);
}
printf ("%d",cnt);
}
int main ()
{
freopen ("dfs.in","r",stdin);
freopen ("dfs.out","w",stdout);
read ();
solve ();
return 0;
}