Pagini recente » Cod sursa (job #1151270) | Cod sursa (job #1333617) | Cod sursa (job #1513367) | Cod sursa (job #352713) | Cod sursa (job #855136)
Cod sursa(job #855136)
#include <string.h>
#include <vector>
#include <list>
#include <stdio.h>
#define Nmax 100000
std::list<int> stack;
std::vector<int> nodes[Nmax];
int n,m;
int vis[Nmax];
void DFS(int Start)
{
stack.push_back(Start);
while(!stack.empty())
{
int i;
int top=stack.back();
if(!vis[top])
{
vis[top]=1;
}
for(i=0;i< nodes[top].size(); i++)
{
if(!vis[nodes[top][i]])
{
stack.push_back(nodes[top][i]);
i=nodes[top].size()+2;
}
}
if(i==nodes[top].size())
{
stack.pop_back();
}
}
}
int main()
{
FILE *f=fopen("dfs.in","r");
fscanf(f,"%d %d",&n,&m);
int a,b;
for(int i=0;i<m;i++)
{
fscanf(f,"%d %d",&a,&b);
nodes[a].push_back(b);
nodes[b].push_back(a);
}
int nrc=0;
for(int i=1;i<=n;i++)
{
if(!vis[i])
{
DFS(i);
nrc++;
}
}
FILE *g=fopen("dfs.out","w");
fprintf(g,"%d",nrc);
return 0;
}