Pagini recente » Istoria paginii runda/winners20/clasament | Istoria paginii runda/iiot45/clasament | Istoria paginii runda/info_cnmv | Istoria paginii runda/pt_round14/clasament | Cod sursa (job #1651170)
#include<iostream>
#include<fstream>
#include<stack>
#include<vector>
using namespace std;
void dfs(const vector<vector<int> > &graph,const int &s,const int &k,vector<int> &visited)
{
visited[s]=k;
stack<int> st;
int elem,i;
bool found;
st.push(s);
while(!st.empty())
{
elem=st.top();
found=false;
for(i=0;i<graph[elem].size() && !found;i++)
{
if(!visited[graph[elem][i]])
found=true;
}
if(found)
{
i--;
st.push(graph[elem][i]);
visited[graph[elem][i]]=k;
}
else st.pop();
}
}
int main()
{
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int v,e,nrconex=0,i,aux1,aux2;
vector<vector<int> > graph;
vector<int> visited;
fin>>v>>e;
graph.resize(v);
visited.resize(v,0);
for(i=0;i<e;i++)
{
fin>>aux1>>aux2;
aux1--;
aux2--;
graph[aux1].push_back(aux2);
graph[aux2].push_back(aux1);
}
for(i=0;i<v;i++)
{
if(!visited[i])
{
nrconex++;
dfs(graph,i,nrconex,visited);
}
}
fout<<nrconex;
return 0;
}