Pagini recente » Cod sursa (job #940074) | Cod sursa (job #2987780) | Cod sursa (job #1340740) | Cod sursa (job #2138084) | Cod sursa (job #940976)
Cod sursa(job #940976)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
vector<vector<int> > adjl;
vector<int> index, lowlink;
stack<int> s;
int num = 0;
vector<vector<int> > ans;
void dfs(int i, int p)
{
s.push(i);
index[i] = lowlink[i] = ++num;
for (vector<int>::iterator it = adjl[i].begin(); it != adjl[i].end(); ++it) {
int v = *it;
if (index[v] == 0) {
dfs(v, i);
if (lowlink[i] > lowlink[v])
lowlink[i] = lowlink[v];
if (index[i] <= lowlink[v]) {
ans.push_back(vector<int>());
while (s.top() != v) {
ans.back().push_back(s.top());
s.pop();
}
s.pop();
ans.back().push_back(v);
ans.back().push_back(i);
}
}
else if (v != p)
if (lowlink[i] > lowlink[v])
lowlink[i] = lowlink[v];
}
}
int main()
{
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n, m;
fin >> n >> m;
adjl.resize(n+1);
index.resize(n+1);
lowlink.resize(n+1);
int u, v;
for (; m > 0; --m) {
fin >> u >> v;
adjl[u].push_back(v);
adjl[v].push_back(u);
}
for (int i = 1; i <= n; ++i)
if (index[i] == 0)
dfs(i,0);
fout << ans.size() << '\n';
for (int i = ans.size()-1; i >= 0; --i) {
for (int j = ans[i].size()-1; j >= 0; --j)
fout << ans[i][j] << ' ';
fout << '\n';
}
return 0;
}