Pagini recente » Cod sursa (job #299547) | Cod sursa (job #1280994) | Cod sursa (job #875628) | Cod sursa (job #2071012) | Cod sursa (job #482511)
Cod sursa(job #482511)
#include<fstream>
#include<iostream>
#include<vector>
#include<stack>
using namespace std;
vector<bool> passed;
int DFS(vector<vector<int> >& graph, int start)
{
if(passed[start])
return 0;
stack<int> st;
st.push(start);
while(!st.empty())
{
int node=st.top();
st.pop();
passed[node]=true;
for(unsigned int i=0; i<graph[node].size(); ++i)
{
if(!passed[graph[node][i]])
st.push(graph[node][i]);
}
}
return 1;
}
int ConexComponents(vector<vector<int> >& graph, int n)
{
int comp=0;
for(int i=1; i<=n; ++i)
{
comp+=DFS(graph,i);
}
return comp;
}
int main()
{
int n,m,x,y;
fstream fin("dfs.in", fstream::in);
fstream fout("dfs.out", fstream::out);
vector<vector<int> >graph;
fin>>n>>m;
graph.resize(n+1);
passed.resize(n+1);
for(int i=0; i<m; ++i)
{
fin>>x>>y;
graph[x].push_back(y);
}
fout<<ConexComponents(graph, n)<<endl;
fin.close();
fout.close();
return 0;
}