Pagini recente » Cod sursa (job #1517066) | Statistici Tantuc Serghei (Tantuc_Serghei_333CB) | Cod sursa (job #1633495) | Cod sursa (job #24281) | Cod sursa (job #972550)
Cod sursa(job #972550)
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
using namespace std;
FILE *f=fopen("dfs.in","r");
FILE *g=fopen("dfs.out","w");
queue <int> q;
stack <int> s;
struct nod{
int v;
nod *next;
};
typedef nod *lista;
int n,m,used[100001];
lista lv[100001];
void readGRAPH()
{
int i,a,b;
lista p;
fscanf(f,"%d%d",&n,&m);
for(i=1;i<=m;++i)
{
fscanf(f,"%d%d",&a,&b);
p=new nod;p->v=a;p->next=lv[b];lv[b]=p;
p=new nod;p->v=b;p->next=lv[a];lv[a]=p;
}
}
void BFS(int k)
{
q.push(k);
used[k]=1;
lista p;
while(!q.empty())
{
for(p=lv[q.front()];p;p=p->next)
if(!used[p->v])used[p->v]=1,q.push(p->v);
q.pop();
}
}
void DFS(int k)
{
s.push(k);
used[k]=1;
lista p;
while(!s.empty())
{
for(p=lv[s.top()];p;p=p->next)
if(!used[p->v])used[p->v]=1,s.push(p->v);
s.pop();
}
}
int main()
{
readGRAPH();
int conex=0;
for(int i=1;i<=n;++i)
if(!used[i])
{
++conex;
//BFS(i);
DFS(i);
}
fprintf(g,"%d",conex);
return 0;
}