Pagini recente » Cod sursa (job #870449) | Cod sursa (job #840106) | Cod sursa (job #2916324) | Cod sursa (job #237505) | Cod sursa (job #974687)
Cod sursa(job #974687)
#include <cstdio>
#include <stack>
#include <queue>
#include <algorithm>
FILE *f=fopen("dfs.in","r");
FILE *g=fopen("dfs.out","w");
using namespace std;
#define x first
#define y second
#define mp make_pair
struct nod{
int v;
nod *next;
};
typedef nod *lista;
stack <int> s;
queue <int> q;
pair <int,int> vrtx[200001];
int n,m,used[100001];
lista lv[100001];
void get_GRAPH()
{
fscanf(f,"%d%d",&n,&m);
int i,a,b;
lista p;
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;
}
}
int pz=0;
int done()
{
for(int i=1;i<=n;++i)
if(!used[i]){pz=i;return 0;}
return 1;
}
void DFS(int k)
{
lista p;
int nodc;
s.push(k);
used[k]=1;
while(!s.empty())
{
nodc=s.top(),s.pop();
for(p=lv[nodc];p;p=p->next)
if(!used[p->v]){used[p->v]=1;s.push(p->v);}
}
}
void BFS(int k)
{
lista p;
int nodc;
q.push(k);
used[k]=1;
while(!q.empty())
{
nodc=q.front(),q.pop();
for(p=lv[nodc];p;p=p->next)
if(!used[p->v])
{
used[p->v]=1;
q.push(p->v);
}
}
}
int main()
{
get_GRAPH();
int nrg=0;
while(!done())
{
//BFS(pz);
DFS(pz);
++nrg;
}
fprintf(g,"%d",nrg);
return 0;
}