Pagini recente » Cod sursa (job #1472327) | Cod sursa (job #1213886) | Soluţii ONIS 2016, Runda 2 | Cod sursa (job #2175881) | Cod sursa (job #1025839)
#include <fstream>
#include <vector>
using namespace std;
struct node
{
int edge;
node *next;
node (int x)
{
edge = x;
next = NULL;
}
};
void add(node *&root, int x)
{
node *aux = new node(x);
aux->next = root;
root = aux;
}
vector < pair < node *, int > > A;
void dfs(int x)
{
A[x].second = 1;
for (node *p = A[x].first; p; p = p->next)
if (!A[p->edge].second)
dfs(p->edge);
}
int main()
{
int n, m, a, b;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
fin>>n>>m;
for (int i = 0; i <= n; ++i)
A.push_back(make_pair( (node *) (NULL), 0));
for (int i = 0; i < m; ++i)
{
fin>>a>>b;
add(A[a].first, b);
add(A[b].first, a);
}
int sol = 0;
for (int i = 1; i <= n; ++i)
if (!A[i].second)
{
dfs(i);
++sol;
}
fout<<sol<<endl;
return 0;
}