Pagini recente » Cod sursa (job #2773885) | Cod sursa (job #541539) | Cod sursa (job #2056651) | Cod sursa (job #2721585) | Cod sursa (job #1455548)
#include <fstream>
#define NMAX 100001
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
int i, n, m, ans=0, x, y;
bool viz[NMAX];
struct node
{
int value;
node *next;
node ()
{
next = NULL;
}
};
node *v[NMAX];
void add(node *&father, int data)
{
node *NewNode = new node;
NewNode -> value = data;
NewNode -> next = father;
father = NewNode;
}
void DFS(int i)
{
viz[i] = 1;
node *Node;
for (Node = v[i]; Node != NULL; Node = Node -> next)
if (!viz[Node -> value]) DFS(Node -> value);
}
int main()
{
f>>n>>m;
for (i=1; i<=m; ++i)
{
f>>x>>y;
add(v[x],y);
add(v[y],x);
}
for (i=1; i<=n; ++i)
if (!viz[i])
{
ans++;
DFS(i);
}
g<<ans<<'\n';
return 0;
}