Pagini recente » Cod sursa (job #2572236) | Rating Dumitrascu Ioana (ioanadum) | Cod sursa (job #1320166) | Cod sursa (job #2483733) | Cod sursa (job #3226070)
#include <iostream>
#include <vector>
#include <fstream>
#define SIZE 100000
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int viz[100000];
struct node{
int nod;
node* prev;
};
node* vertex[SIZE];
void add(node** head, int neighbor){
node *x = (node*)malloc(sizeof(node));
x->nod = neighbor;
x->prev = *head;
*head = x;
}
void DFS(int x){
node* head = vertex[x];
while(head){
viz[head->nod] = 1;
head = head->prev;
}
}
int N, M;
int main(){
fin >> N >> M;
for(int i = 0; i<M; i++){
int x, y;
fin >> x >> y;
add(&vertex[x], y);
}
int componente = 0;
for(int i = 1; i<=N; i++){
if(viz[i] == 1)
continue;
DFS(i);
componente++;
}
fout << componente;
}