Cod sursa(job #1618343)

Utilizator AvramAlexandraAvram Ioana-Alexandra AvramAlexandra Data 27 februarie 2016 19:42:42
Problema Parcurgere DFS - componente conexe Scor 55
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <fstream>

using namespace std;

ifstream f("dfs.in");
ofstream g("dfs.out");

struct
{
    int x,y;
}v[100001];
int x,y,m,i,n,d[100001],nr,minim,maxim,j,k,max1,max2,poz,poz1;

int main()
{
     f>>n>>m;
   for(i=1;i<=m;i++)
   {
      f>>x>>y;
    v[i].x=x,v[i].y=y;
   }
   for(i=1;i<=n;i++) d[i]=i;

    for(i=1;i<=m;i++)
       if(d[v[i].x]!=d[v[i].y])
    {
        if(d[v[i].x]<d[v[i].y])
        {
        minim=d[v[i].x];
        maxim=d[v[i].y];
        }
            else
            {
                minim=d[v[i].y];
                maxim=d[v[i].x];
            }
       for(j=1;j<=n;j++)
        if(d[j]==maxim) d[j]=minim;
    }
    for(i=1;i<=n;i++)
        if(d[i])
    {
    k++;
        for(j=i+1;j<=n;j++)
            if(d[i]==d[j])d[j]=0;
    }
  g<<k;
    return 0;
}