Pagini recente » Cod sursa (job #1285717) | Cod sursa (job #790514) | Cod sursa (job #746294) | Cod sursa (job #94570) | Cod sursa (job #633589)
Cod sursa(job #633589)
#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);
}
for(i=1;i<=n;i++)
if(viz[i]==0) {
conexe++;
DFS(i);
}
fprintf(g,"%d",conexe);
fclose(f);
fclose(g);
return 0;
}