Pagini recente » Cod sursa (job #429925) | Cod sursa (job #383246) | Cod sursa (job #2784177) | Cod sursa (job #1394177) | Cod sursa (job #1338453)
#include <cstdio>
#include <vector>
#include <stack>
#define N 100010
using namespace std;
vector<int> arcs[N];
int visited[N];
int n,m;
int readInt()
{
int n=0;
char c = getchar();
while(c<'0'|| c>'9') c=getchar();
while(c>='0' && c<='9')
{
n=(n<<1)+(n<<3)+c-'0';
c=getchar();
}
return n;
}
void ReadFile()
{
freopen("dfs.in", "r", stdin);
int a,b;
n=readInt();
m=readInt();
for(int i=1;i<=m;++i)
{
a=readInt();
b=readInt();
arcs[a].push_back(b);
arcs[b].push_back(a);
}
for(int i=1;i<=n;++i)
{
visited[i]=0;
}
}
void Dfs(int nS)
{
vector<int>::iterator it;
stack<int> stk;
stk.push(nS);
visited[nS]=1;
while(!stk.empty())
{
int p=stk.top();
stk.pop();
for(it=arcs[p].begin();it!=arcs[p].end();++it)
{
if(visited[*it]==0)
{
visited[*it]=1;
stk.push(*it);
}
}
}
}
void Solve()
{
freopen("dfs.out", "w", stdout);
int res=0;
for(int i=1;i<=n;++i)
{
if(visited[i]==0)
{
Dfs(i);
res++;
}
}
printf("%d\n",res);
}
int main()
{
ReadFile();
Solve();
return 0;
}