Pagini recente » Cod sursa (job #1682644) | Diferente pentru preoni-2005/runda-1/solutii intre reviziile 30 si 29 | Cod sursa (job #2521825) | Statistici fdsfasdfasdfasd (valoare_swag) | Cod sursa (job #3227218)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int n, m, node1, node2, vis[100005], cnt;
vector<vector<int>> graf;
void ct()
{
fin >> n >> m;
graf.resize(n + 1);
for(int i = 1; i <= m; i++)
{
fin >> node1 >> node2;
graf[node1].push_back(node2);
graf[node2].push_back(node1);
}
}
void afis()
{
for(int i = 1; i <= n; i++)
{
for(int j = 0; j < graf[i].size(); j++)
fout << graf[i][j] << ' ';
fout << endl;
}
}
void dfs(int nodestart)
{
int node;
stack<int> st;
st.push(nodestart);
while(!st.empty())
{
node = st.top();
//fout << node << ' ';
st.pop();
for(int i = 0; i < graf[node].size(); i++)
{
if(!vis[graf[node][i]])
{
vis[graf[node][i]] = 1;
st.push(graf[node][i]);
}
}
}
}
void bfs(int nodestart)
{
queue<int> q;
q.push(nodestart);
int node;
while(!q.empty())
{
node = q.front();
q.pop();
for(int i = 0; i < graf[node].size(); i++)
{
if(!vis[graf[node][i]])
{
vis[graf[node][i]] = 1;
q.push(graf[node][i]);
}
}
}
}
int main()
{
ct();
//afis();
for(int i = 1; i <= n; i++)
{
if(!vis[i])
{
vis[i] = 1;
dfs(i);
cnt++;
}
}
fout << cnt;
return 0;
}