Pagini recente » Cod sursa (job #1628876) | Cod sursa (job #1010377) | Cod sursa (job #147508) | Cod sursa (job #1871544) | Cod sursa (job #3123313)
#include <fstream>
#include <vector>
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
typedef vector<vector<int>> Graph;
void dfsRec(Graph &adj,int n,vector<bool> &visited,vector<int> &top,int &nr)
{
visited[n]=true;
for(auto neigh : adj[n])
if(!visited[neigh])
dfsRec(adj,neigh,visited,top,nr);
top[--nr]=n;
}
void dfs(Graph &adj,int n)
{
int nr=n,ret=0;
vector<bool> visited(n+1,false);//daca a fost vizitat nodul
vector<int> top(n);//ordinea topologica
for(int i=1;i<=n;++i)
if(!visited[i])
ret++,dfsRec(adj,i,visited,top,nr);
g<<ret<<'\n';
}
int main()
{
int n,m,i,x,y;
f>>n>>m;
Graph adj(n+1,vector<int>());
for(i=0;i<m;i++)
{
f>>x>>y;
adj[x].push_back(y);
adj[y].push_back(x);
}
dfs(adj,n);
f.close();
g.close();
}