Cod sursa(job #974692)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 17 iulie 2013 22:54:56
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
#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;
}