Cod sursa(job #220321)

Utilizator Bogdan_CCebere Bogdan Bogdan_C Data 10 noiembrie 2008 14:41:43
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <fstream>
#define MAX(a, b) ((a) < (b) ? (b) : (a))
#define MIN(a, b) ((a) < (b) ? (a) : (b))
using namespace::std;

ifstream in("dfs.in");
 ofstream out("dfs.out");
   int n,m,c[100000],xmin,xmax;
struct graf
{int x,y;} g[200000];

void citire()
{in>>n>>m;
for(int i=0;i<m;i++)
{in>>g[i].x;in>>g[i].y;}
in.close();
}
void desc()
{int i;
for(i=1;i<=n;i++)
 c[i]=i;
for(int j=0;j<m;j++)
{if(c[g[j].x]!=c[g[j].y])
   {xmin=MIN(c[g[j].x],c[g[j].y]);
     xmax=MAX(c[g[j].x],c[g[j].y]);}
    for(i=1;i<=n;i++)
     if(c[i]==xmax) c[i]=min; } }
 void afisare()
 {int nrc=0;
 for(int i=1;i<=n;i++)
 {if(c[i]!=0)
  {nrc++;
    for(int j=i+1;j<=n;j++)
     if(c[i]==c[j]) c[j]=0;}}
     out<<nrc;
     out.close();
 }
int main()
{    citire();
     desc();
     afisare();

      system("PAUSE");
      return 0;
}