Pagini recente » Statistici Marin Victor (voinicel) | Cod sursa (job #223706) | Statistici Lucia Clark (pestcontrol689) | Cod sursa (job #2660147) | Cod sursa (job #1569229)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin ("dfs.in");
ofstream fout ("dfs.out");
typedef struct path {int x; path *y; /*linked path*/} *LinkedPath;
LinkedPath edge[100005];
int visited[100005],n,m;
void add (LinkedPath &source, int DestNode)
{
LinkedPath temp;
temp = new path;
temp->x = DestNode;
temp->y = source;
source = temp;
}
void DFS (int node)
{
LinkedPath temp;
visited[node]=1;
for (temp = edge[node]; temp != NULL; temp=temp->y)
if (!visited[temp->x])
DFS(temp->x);
}
int main()
{
int x,y,counter;
fin >>n >>m;
for (int i = 1; i <= m; ++i)
{
fin >>x >>y;
add(edge[x],y);
add(edge[y],x); /* Adds backwards edge*/
}
counter = 0;
for (int i = 1; i <= n; ++i)
if (!visited[i])
{
++counter;
DFS(i);
}
fout <<counter <<'\n';
return 0;
}