Pagini recente » Cod sursa (job #1877351) | Cod sursa (job #2075909) | Cod sursa (job #2093541) | Cod sursa (job #1667535) | Cod sursa (job #290261)
Cod sursa(job #290261)
#include<iostream>
#include<stdio.h>
#include<stack>
using namespace std;
struct nod {int inf;nod *next;} *a[100010],*p;
stack<int> st;
int n,m,i,ut[100010],nr,x,y;
int main()
{
freopen("dfs.in","r",stdin);
freopen("dfs.out","w",stdout);
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
p=new nod; p->next=a[x];p->inf=y;a[x]=p;
p=new nod; p->next=a[y];p->inf=x;a[y]=p;
}
for(i=1;i<=n;i++)
if(!ut[i])
{
nr++;
st.push(i);
while(!st.empty())
{
for(p=a[st.top()];p;p=p->next)
if(!ut[p->inf])
st.push(p->inf);
if(!ut[st.top()])
ut[st.top()]=1;
else
st.pop();
}
}
printf("%d\n",nr);
return 0;
}