Pagini recente » Cod sursa (job #2332480) | Cod sursa (job #750151) | Cod sursa (job #1821597) | Cod sursa (job #2472330) | Cod sursa (job #645828)
Cod sursa(job #645828)
#include <fstream>
#include <queue>
#include <stack>
#define NMAX 100000
using namespace std;
int n, m, s;
int viz[NMAX + 1];
struct node{
int inf;
node* next;
} *G[NMAX + 1];
void add(int list, int x){
node *p = new node;
p->inf = x;
p->next = G[list];
G[list] = p;
}
void bfs(int s, int cc){
stack<int> q;
int x;
q.push(s);
viz[s] = cc;
while(!q.empty()){
x = q.top();
q.pop();
for(node *p = G[x]; p; p = p->next){
if(!viz[p->inf]){
q.push(p->inf);
viz[p->inf] = viz[x];
}
}
}
}
int main()
{
ifstream f("dfs.in");
ofstream g("dfs.out");
f >> n >> m;
int i, x, y;
for(i = 0; i < m; ++i){
f >> x >> y;
add(x, y);
add(y, x);
}
int cc = 0;
for(i = 1; i <= n; i++)
if(!viz[i])
bfs(i, ++cc);
/*
for(i = 1; i <= n; ++i)
g << viz[i] - 1 << " ";
*/
g << cc << "\n";
f.close();
g.close();
return 0;
}