Cod sursa(job #2265986)

Utilizator SmokeCiocotisan Cosmin Smoke Data 21 octombrie 2018 23:23:36
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include <iostream>
#include <fstream>
using namespace std;
int n,m;
int c[100];


struct m{
 int x,y;

}v[100];

 void citire()
 {ifstream in("dfs.in");
     in>>n>>m;
     for(int i=0;i<m;i++)
        in>>v[i].x>>v[i].y;


 }

 void  comp_conexe()
 {int min,max;
     for(int i=1;i<=n;i++)
        c[i]=i;

     for(int i=0;i<m;i++)
  if(c[v[i].x] != c[v[i].y])
     {
         if(c[v[i].x] > c[v[i].y]){ min=c[v[i].y] ;max=c[v[i].x] ;}
          else
            {min=c[v[i].x] ;max=c[v[i].y] ;}

          for(int l=1;l<=n;l++)
            if(c[l]==max) c[l]=min;

     }




 }


int main()
{int nr=0;
citire();
comp_conexe();
  for(int i=1;i<=n;i++)
  { if(c[i])
     {nr++;
            for(int j=i+1;j<=n;j++)
          if(c[i]==c[j])  c[j]=0;


     }

  }
ofstream out("dfs.out");
out<<nr;



    return 0;
}