Pagini recente » Cod sursa (job #446514) | Clasament hc_round9 | Clasament rf1 | Cod sursa (job #876670) | Cod sursa (job #2005645)
#include <fstream>
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
const int N = 100005;
struct nod{
int nr;
nod *urm;
}*v[N];
int st[N];
bool ver[N];
void adaug(int x, int y){
nod *p = new nod;
nod *q = new nod;
p->nr = y;
p->urm = v[x];
v[x] = p;
q->nr = x;
q->urm = v[y];
v[y] = q;
}
int dfs(int n, int ns){
int l = 0, val, vf;
bool g;
st[++l] = ns;
ver[ns] = true;
while(l > 0){
g = 0;
vf = st[l];
for(nod *nou = v[vf];nou && g == 0;nou = nou->urm){
val = nou->nr;
if(ver[val] == false){
ver[val] = true;
st[++l] = vf = val;
g = 1;
}
}
if(g == 0)
vf = st[--l];
}
}
int main()
{
int n,m,x,y,cnt = 0;
in>>n>>m;
for(int i=1;i<=m;i++){
in>>x>>y;
adaug(x,y);
}
in.close();
for(int i=1;i<=n;i++)
if(ver[i] == false){
cnt++;
dfs(n,i);
}
out<<cnt<<"\n";
out.close();
return 0;
}