Pagini recente » Cod sursa (job #831439) | Cod sursa (job #108085) | Cod sursa (job #1693374) | Cod sursa (job #2250180) | Cod sursa (job #1733792)
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
typedef struct node{
int name;
node* next;
}*nodep;
nodep graphList[100005];
bool trecut[100005];
int n, m;
int x, y;
int conex;
void add(nodep &n, int val)
{
nodep p = new node;
p->name = val;
p->next = n;
n = p;
}
void DFS(int poz)
{
trecut[poz] = true;
for(nodep i=graphList[poz]; i!= NULL; i=i->next){
if(!trecut[i->name]){
DFS(i->name);
}
}
}
int main()
{
in >> n >> m;
for(int i=0; i<m; i++){
in >> x >> y;
add(graphList[x], y);
add(graphList[y], x);
}
for(int j=0; j<n; j++){
if(!trecut[j]){
conex++;
DFS(j);
}
}
out << conex << '\n';
return 0;
}