Cod sursa(job #662249)

Utilizator galbenugalbenu dorin galbenu Data 16 ianuarie 2012 11:26:23
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include<iostream>
#include<fstream>
#include<cstring>
#define nmax 100010
using namespace std;
ifstream f("dfs.in",fstream::in);
ofstream g("dfs.out",fstream::out);
struct nod
{unsigned int inf;
 nod *urm;
};
nod *L[nmax];
bool viz[nmax];
unsigned int n,m;
void DF(unsigned int i)
{nod *p;
 viz[i]=1;
  for(p=L[i];p;p=p->urm)
	   if(!viz[p->inf])
		    DF(p->inf);
}
void add(unsigned int x,unsigned int y)
{ nod *nou;
  nou=new nod;
  nou->inf=x;
  nou->urm=L[y];
  L[y]=nou;
}
void read()
{unsigned int i,x,y;
 f>>n>>m;
 for(i=1;i<=m;i++)
	 f>>x>>y,add(y,x);
}
void show()
{
 unsigned int i;
 nod *p;
  for(i=1;i<=n;i++)
  {cout<<i<<" "; 
   for(p=L[i];p;p=p->urm)
	   cout<<p->inf<<" ";
   cout<<"\n";
  }
  cout<<"\n\n";
}
unsigned int solve()
{unsigned int contor=0,i;
 for(i=1;i<=n;i++)
	  if(!viz[i])
		  DF(i),contor++;
	return contor;
}
int main()
{read();
 //show();
g<<solve();
 f.close();
 g.close();
 return 0;
}