Pagini recente » Cod sursa (job #3206722) | Cod sursa (job #2935536) | Cod sursa (job #526837) | Cod sursa (job #826978) | Cod sursa (job #1782697)
#include<fstream>
#include<algorithm>
#include<vector>
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
vector<int> G[100010];
vector<int> rez[100010];
vector<int> stk;
int v[100010][2],nr,viz[1000010], rez_nr=1;
void tarjan(int x, int f)
{
viz[x] = 1;
for (int i = 0;i < G[x].size();++i)
if (!viz[G[x][i]])
{
v[G[x][i]][0] = ++nr;
v[G[x][i]][1] = ++nr;
tarjan(G[x][i], x);
v[x][1] = min(v[G[x][i]][1], v[x][1]);
if (v[x][0] <= v[G[x][i]][1])
{
while (stk.size() && stk.back() != x)
rez[rez_nr].push_back(stk.back()), stk.pop_back();
rez[rez_nr].push_back(x);
++rez_nr;
stk.push_back(x);
}
}
else if (G[x][i] != f)
{
v[x][1] = min(v[G[x][i]][1], v[x][1]);
}
}
int main()
{
int N, M;
in >> N >> M;
for (int i = 1;i <= M;++i)
{
int x, y;
in >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
for (int i = 1;i <= N;++i)
if (!viz[i])
tarjan(i, 0);
--rez_nr;
out << rez_nr << '\n';
for (int i = 1;i <= rez_nr;++i)
{
for (int j = 0;j < rez[i].size();++j)
out << rez[i][j] << " ";
out << '\n';
}
return 0;
}