Pagini recente » Cod sursa (job #187315) | Cod sursa (job #2334513) | Cod sursa (job #3131485) | Cod sursa (job #2020761) | Cod sursa (job #1104804)
#include<fstream>
#define N 100005
using namespace std;
struct Node {
int val;
Node *next;
};
ifstream f("dfs.in");
ofstream g("dfs.out");
void insert(Node *&top, int val)
{
Node *newTop = new Node();
newTop -> next = top;
newTop -> val = val;
top = newTop;
}
void dfs(int s, Node *A[], int* viz)
{
viz[s] = 1;
for(Node *it = A[s]; it; it = it -> next)
{
if (!viz[it->val])
{
dfs(it->val, A, viz);
}
}
}
int main()
{
int n, m;
Node *A[N];
f >> n >> m;
int *viz = new int[n + 5];
for(int i = 1; i <= n; i++)
{
A[i] = 0;
viz[i] = 0;
}
for(int i = 1; i <= m; i++)
{
int x, y;
f >> x >> y;
insert(A[x], y);
insert(A[y], x);
}
int connected = 0;
for(int i = 1; i <= n; i++)
{
if (!viz[i])
{
dfs(i, A, viz);
connected++;
}
}
g << connected;
}