Pagini recente » Cod sursa (job #2534255) | Cod sursa (job #2227849) | Cod sursa (job #1858304) | Cod sursa (job #2235839) | Cod sursa (job #974692)
Cod sursa(job #974692)
#include <cstdio>
#include <algorithm>
#include <list>
#include <queue>
#include <stack>
#define mp make_pair
#define pb push_back
#define x first
#define y second
FILE *f=fopen("dfs.in","r");
FILE *g=fopen("dfs.out","w");
using namespace std;
queue <int> q;
stack <int> s;
pair <int,int> vrtx[200001];
list <int> lv[1000001];
list <int> ::iterator it;
int n,m,used[100001],pz;
void get_GRAPH()
{
fscanf(f,"%d%d",&n,&m);
int i,a,b;
for(i=1;i<=m;++i)fscanf(f,"%d%d",&a,&b),a < b ? vrtx[i]=mp(a,b) : vrtx[i]=mp(b,a);
sort(vrtx+1,vrtx+m+1);
for(i=1;i<=m;++i)
if(vrtx[i].x!=vrtx[i].y&&(vrtx[i-1].x!=vrtx[i].x||vrtx[i-1].y!=vrtx[i].y))
lv[vrtx[i].x].pb(vrtx[i].y),lv[vrtx[i].y].pb(vrtx[i].x);
}
int ready()
{
int i;
for(i=1;i<=n;++i)
if(used[i]==0){pz=i;return 0;}
return 1;
}
void DFS(int k)
{
s.push(k);
used[k]=1;
int crt;
while(!s.empty())
{
crt=s.top();s.pop();
for(it=lv[crt].begin();it!=lv[crt].end();++it)
if(!used[*it]){used[*it]=1;s.push(*it);}
}
}
void BFS(int k)
{
used[k]=1;
q.push(k);
int crt;
while(!q.empty())
{
crt=q.front(),q.pop();
for(it=lv[crt].begin();it!=lv[crt].end();++it)
if(!used[*it])
{
used[*it]=1;
q.push(*it);
}
}
}
int main()
{
get_GRAPH();
int nrg=0,i;
for(i=1;i<=n;++i)
if(!used[i])
DFS(i),++nrg;
//BFS(pz),++nrg;
fprintf(g,"%d",nrg);
return 0;
}