Pagini recente » Cod sursa (job #501903) | Cod sursa (job #345437) | Cod sursa (job #106693) | Cod sursa (job #1223758) | Cod sursa (job #771761)
Cod sursa(job #771761)
#include<fstream>
using namespace std;
int n,m,gata,gasit;
struct lista
{int nod;
lista* next;};
lista* a[100001];
void add(int x, int y)
{lista* q = new lista;
q->nod=y;
q->next=a[x];
a[x]=q;}
ifstream f("dfs.in");
ofstream g("dfs.out");
int i,viz[100001], stack[100001], end, nrconex,s;
void depth(int e)
{lista* q=a[e];
while(q)
{if(viz[q->nod]==0)
{viz[q->nod]=nrconex;
depth(q->nod);}
q=q->next;}
}
int main()
{f>>n>>m;
int x,y;
for( i=1; i<=m; i++)
{f>>x>>y;
add(x,y);
add(y,x);}
nrconex=0;
while(gata==0)
{gata=1;
for(i=1; i<=n; i++)
if(viz[i]==0)
{s=i;
gata=0;
nrconex++;
break;}
if(gata==0)
{viz[s]=nrconex;
depth(s);}
}
g<<nrconex;
f.close();
g.close();
return 0;}