Pagini recente » Cod sursa (job #1056662) | Cod sursa (job #1568799) | Cod sursa (job #2573813) | Cod sursa (job #939194) | Cod sursa (job #2347194)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
std::ifstream fin ("biconex.in");
std::ofstream fout ("biconex.out");
const int MaxN = 100001;
int n, m;
std::vector<int> v[MaxN];
std::stack<int> st;
int low[MaxN];
int level[MaxN];
bool seen[MaxN];
std::vector<int> sol[MaxN];
int nrComponente;
void ReadData();
void DFS(int x);
void Solve();
void Write();
int main ()
{
ReadData();
Solve();
Write();
fin.close();
fout.close();
return 0;
}
void ReadData()
{
fin >> n >> m;
int x, y;
for (int i = 1; i <= m; ++i)
{
fin >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}
}
void DFS(int x)
{
seen[x] = true;
low[x] = level[x];
st.push(x);
for (size_t i = 0; i < v[x].size(); ++i)
{
int neigh = v[x][i];
if (seen[neigh] == true)
{
low[x] = std::min(low[x], level[neigh]);
continue;
}
level[neigh] = level[x] + 1;
DFS(neigh);
low[x] = std::min(low[x], low[neigh]);
if (low[neigh] >= level[x])
{
nrComponente++;
sol[nrComponente].push_back(x);
int x = 0;
do
{
x = st.top();
st.pop();
sol[nrComponente].push_back(x);
} while(x != neigh);
}
}
}
void Solve()
{
for (int i = 1; i <= n; ++i)
{
if (!seen[i])
{
level[i] = 1;
DFS(i);
}
}
}
void Write()
{
fout << nrComponente << '\n';
for (int i = 1; i <= nrComponente; i++)
{
for (size_t k = 0; k < sol[i].size(); k++)
{
fout << sol[i][k] << " ";
}
fout << "\n";
}
}