Pagini recente » Cod sursa (job #833200) | Cod sursa (job #1998064) | Cod sursa (job #974262) | Cod sursa (job #2117249) | Cod sursa (job #765377)
Cod sursa(job #765377)
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream F("dfs.in");
ofstream G("dfs.out");
#define Mmax 200011
#define Nmax 100011
#define mark(i) ( Marked[i]=1 )
#define unmark(i) ( Marked[i]=0 )
vector<int> Leg[Mmax];
int Marked[Mmax];
int N,M,Comp;
void DF(int Nod)
{
for ( register unsigned int i=0; i< Leg[Nod].size(); ++i)
if ( !Marked[Leg[Nod][i]] )
{
Marked[Leg[Nod][i]]=1;
DF(Leg[Nod][i]);
}
}
int main()
{
F>>N>>M;
for (int i=1;i<=M;++i)
{
int x,y;
F>>x>>y;
Leg[x].push_back(y);
Leg[y].push_back(x);
}
for (int i=1;i<=N;++i)
if ( !Marked[i] )
{
mark(i);
++Comp;
DF(i);
}
G<<Comp<<'\n';
}