Pagini recente » Cod sursa (job #1299783) | Cod sursa (job #2943610) | Cod sursa (job #219507) | Cod sursa (job #2645717) | Cod sursa (job #633592)
Cod sursa(job #633592)
#include<stdio.h>
#include<vector>
#include<stack>
using namespace std;
FILE *f,*g;
vector<int> a[100001];
int viz[100001],n,m;
void DFS(int v)
{
stack<int> s;
int j,primul;
bool k;
s.push(v);
viz[v]=1;
while(s.empty()==0) {
primul=s.top();
k=0;
for(j=0;j<a[primul].size()&&k==0;j++)
if(viz[a[primul][j]]==0)
k=1;
if(k==1) {
j--;
s.push(a[primul][j]);
viz[a[primul][j]]=1;
}
else
s.pop();
}
}
int main()
{
int i,x,y,conexe=0;
f=fopen("dfs.in","r");
g=fopen("dfs.out","w");
fscanf(f,"%d %d",&n,&m);
for(i=1;i<=m;i++) {
fscanf(f,"%d %d",&x,&y);
a[x].push_back(y);
a[y].push_back(x);
}
for(i=1;i<=n;i++)
if(viz[i]==0) {
DFS(i);
conexe++;
}
fprintf(g,"%d",conexe);
fclose(f);
fclose(g);
return 0;
}