Cod sursa(job #668263)

Utilizator timeiutzaTimea Balan timeiutza Data 24 ianuarie 2012 17:04:37
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb

#include <fstream>
#include <vector>
using namespace std;
const int MAXSIZE = 100001;
ifstream in("dfs.in");
ofstream out("dfs.out");
int nodes,edges,answer;
bool visited[MAXSIZE];
vector<int> graph[MAXSIZE];
void depthFirst(int node);
int main()
{
in >> nodes >> edges;
int from,to;
for(int i=1;i<=edges;i++)
{
in >> from >> to;
graph[from].push_back(to);
graph[to].push_back(from);
}
in.close();
for(int i=1;i<=nodes;i++)
if(!visited[i])
{
depthFirst(i);
answer++;
}
out << answer << "\n";
out.close();
return (0);
}
void depthFirst(int node)
{
vector<int>::iterator end = graph[node].end();
visited[node] = true;
for(vector<int>::iterator it=graph[node].begin();it!=end;++it)
if(!visited[*it])
depthFirst(*it);
}