Pagini recente » Cod sursa (job #1506497) | Cod sursa (job #1431136) | Cod sursa (job #1652865) | Cod sursa (job #1051882) | Cod sursa (job #2203954)
#include <cstdio>
#include <vector>
using namespace std;
vector < vector <int> > adia;
vector <int> parinte;
vector <char> culori;
int n, m, nrc;
void citire();
void initializare(int val);
void dfs();
void dfs_viz(int s);
int main(){
citire();
dfs();
return 0;
}
void initializare(int val){
adia.resize(val + 10);
culori.resize(val + 10);
parinte.resize(val + 10);
for(int i = 1; i <= val; i++)
adia[i].push_back(0);
}
void citire(){
FILE* f = fopen("dfs.in", "r");
fscanf(f, "%d%d", &n, &m);
initializare(n);
int x, y;
for(int i = 0; i < m; i++){
fscanf(f, "%d%d", &x, &y);
adia[x][0]++;
adia[x].push_back(y);
adia[y][0]++;
adia[y].push_back(x);
}
fclose(f);
}
void dfs(){
for(int i = 1; i <= n; i++){
culori[i] = 'a';
parinte[i] = 0;
}
for(int i = 1; i <= n; i++){
if(culori[i] == 'a'){
nrc++;
dfs_viz(i);
}
}
FILE* f = fopen("dfs.out", "w");
fprintf(f, "%d", nrc);
fclose(f);
}
void dfs_viz(int s){
culori[s] = 'g';
for(int i = 1; i <= adia[s][0]; i++)
if(culori[adia[s][i]] == 'a'){
parinte[adia[s][i]] = s;
dfs_viz(adia[s][i]);
}
culori[s] = 'n';
}