Pagini recente » Cod sursa (job #1783213) | Cod sursa (job #1026181) | Cod sursa (job #1979588) | Cod sursa (job #2470745) | Cod sursa (job #2470535)
#include <bits/stdc++.h>
using namespace std;
stack<size_t> nodeStack;
vector<vector<size_t>> graph(100001, vector<size_t>());
vector<vector<size_t>> bks;
size_t id[100001], lv[100001], N, M;
void dfs(size_t node, size_t parent)
{
id[node] = lv[node] = id[parent] + 1;
nodeStack.push(node);
for(auto& next : graph[node])
{
if(!id[next])
{
dfs(next, node);
lv[node] = min(lv[node], lv[next]);
if(id[node] <= lv[next])
{
vector<size_t> bk;
bk.push_back(node);
bk.push_back(next);
while(nodeStack.top() != next)
{
bk.push_back(nodeStack.top());
nodeStack.pop();
}
nodeStack.pop();
bks.push_back(bk);
}
} else if(next != parent) lv[node] = min(lv[node], id[next]);
}
}
int main()
{
ifstream fin("biconex.in");
ofstream fout("biconex.out");
fin >> N >> M;
size_t x, y;
for(; M; M--)
{
fin >> x >> y;
graph[x].push_back(y);
graph[y].push_back(x);
}
for(size_t i = 1; i <= N; ++i)
{
if(!id[i]) dfs(i, 0);
}
fout << bks.size() << '\n';
for(auto& bk : bks)
{
for(auto& node : bk) fout << node << ' ';
fout << '\n';
}
}