Pagini recente » Cod sursa (job #2872241) | Cod sursa (job #2499775) | Cod sursa (job #2885034) | Cod sursa (job #764872) | Cod sursa (job #846430)
Cod sursa(job #846430)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
const char iname[] = "dfs.in";
const char oname[] = "dfs.out";
ifstream fin(iname);
ofstream fout(oname);
int N , M , i , j , x , y , comp_conexe , gasit;
bool viz[ 100004 ];
vector < int > Q[ 100004 ];
stack < int > st;
int main()
{
fin >> N >> M;
for (i = 1; i <= M; ++i)
fin >> x >> y , Q[x].push_back(y) , Q[y].push_back(x);
vector < int > :: iterator it;
for (i = 1; i <= N; ++i)
{
if (!viz[i])
{
viz[i] = 1;
st.push(i);
while(!st.empty())
{
x = st.top();
gasit = 0;
while(!Q[x].empty())
{
if (!viz[Q[x].front()])
{
it = Q[x].begin();
st.push(*it);
viz[*it] = 1;
Q[x].erase(Q[x].begin());
gasit = 1;
break;
}
else
Q[x].erase(Q[x].begin());
}
if (!gasit)
st.pop();
}
++comp_conexe;
}
}
fout << comp_conexe << '\n';
return 0;
}