Pagini recente » Cod sursa (job #2341728) | Cod sursa (job #1768431) | Rating Dirdeci Ana (anaaaqd) | Cod sursa (job #1615909) | Cod sursa (job #1481549)
#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <stack>
using namespace std;
#define MAX 100005
int n, m, nrCompCon = 1, i, a, b, conn[MAX], current, adListSize,lastVisited;
vector<int> graph[MAX];
stack<int> mySt;
int main()
{
freopen("dfs.in", "r", stdin);
freopen("dfs.out", "w", stdout);
scanf("%d%d", &n, &m);
memset(conn, -1, (n+1)*4);
for (i = 0; i < m; ++i) scanf("%d%d", &a, &b), graph[a].push_back(b), graph[b].push_back(a);
mySt.push(1);
lastVisited = 1;
conn[1] = 1;
while (mySt.size()>0 || lastVisited <= n)
{
if (mySt.size()>0) current = mySt.top(),mySt.pop();
else
{
while (++lastVisited <= n)
{
if (conn[lastVisited] == -1) current = lastVisited;
break;
}
if (lastVisited > n) break;
}
adListSize = graph[current].size();
if (conn[current] == -1) conn[current] = ++nrCompCon;
adListSize = graph[current].size();
for (i = 0; i < adListSize; ++i)
if (conn[graph[current][i]]==-1) conn[graph[current][i]] = conn[current],mySt.push(graph[current][i]);
}
printf("%d", nrCompCon);
}