Pagini recente » Cod sursa (job #18689) | Cod sursa (job #2270337) | Cod sursa (job #375589) | Cod sursa (job #2931435) | Cod sursa (job #220321)
Cod sursa(job #220321)
#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;
}