Pagini recente » Cod sursa (job #633839) | Cod sursa (job #1201850) | Cod sursa (job #2400303) | Cod sursa (job #308219) | Cod sursa (job #2564609)
#include <vector>
#include <bitset>
#include <stack>
#include <fstream>
#include <algorithm>
using namespace std;
const int NMAX = 100005;
int N, M;
vector <int> graph[NMAX];
bitset <NMAX> seen;
int low[NMAX], h[NMAX];
stack <int> st;
vector < vector <int> > answer;
void dfs(int node, int father)
{
low[node] = h[node] = h[father] + 1;
seen[node] = 1;
st.push(node);
for (auto& son : graph[node])
{
if (son == father)
continue;
if (seen[son] == 1)
{
///backedge
low[node] = min(low[node], h[son]);
continue;
}
dfs(son, node);
low[node] = min(low[node], low[son]);
if (low[son] >= h[node])
{
vector <int> bic;
int x;
do
{
x = st.top();
st.pop();
bic.push_back(x);
} while (x != son);
bic.push_back(node);
answer.push_back(bic);
}
}
}
int main()
{
ifstream fin("biconex.in");
ofstream fout("biconex.out");
fin >> N >> M;
for (int i = 1; i <= M; ++i)
{
int u, v;
fin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
for (int i = 1; i <= N; ++i)
if (seen[i] == 0)
dfs(i, 0);
fout << answer.size() << "\n";
for (auto& i : answer)
{
for (auto& j : i)
fout << j << " ";
fout << "\n";
}
fin.close();
fout.close();
return 0;
}