Pagini recente » Cod sursa (job #395673) | Cod sursa (job #1130559) | Cod sursa (job #1685333) | Cod sursa (job #1774455) | Cod sursa (job #858621)
Cod sursa(job #858621)
#include <fstream>
#define nmax 100001
using namespace std;
struct nod_lista{
int vecin;
nod_lista *link;
};
nod_lista *G[nmax];
int Viz[nmax];
int N,M,nCmp;
void adauga(int unde,int ce)
{
nod_lista *q=new nod_lista;
q->vecin=ce;
q->link=G[unde];
G[unde]=q;
}
void citeste()
{
ifstream f("dfs.in");
int i,x,y;
f>>N>>M;
for(i=1;i<=M;i++)
{
f>>x>>y;
adauga(x,y);
adauga(y,x);
}
f.close();
}
void DFS(int nod)
{
Viz[nod]=1;
nod_lista *q=G[nod];
while(q)
{
if(!Viz[q->vecin])
DFS(q->vecin);
q=q->link;
}
}
void rezolva()
{
int i;
for(i=1;i<=N;i++)
if(!Viz[i])
{
++nCmp;
DFS(i);
}
}
void scrie()
{
ofstream g("dfs.out");
g<<nCmp<<'\n';
g.close();
}
int main()
{
// cout << "Hello world!" << endl;
citeste();
rezolva();
scrie();
return 0;
}