Pagini recente » Borderou de evaluare (job #1681738) | Borderou de evaluare (job #2353670) | Borderou de evaluare (job #1572781) | Borderou de evaluare (job #1736503) | Cod sursa (job #2564599)
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
vector<int> G[100010], biconex[100010], stk;
int N, M, viz[100010], n_time[100010], min_time[100010], tm, nr;
void tarjan(int x, int f)
{
viz[x] = 1;
stk.push_back(x);
for (int i = 0; i < G[x].size(); ++i)
if (!viz[G[x][i]])
{
n_time[G[x][i]] = min_time[G[x][i]] = ++tm;
tarjan(G[x][i], x);
if (n_time[x] <= min_time[G[x][i]])
{
++nr;
while (stk.back() != G[x][i])
biconex[nr].push_back(stk.back()), stk.pop_back();
stk.pop_back();
biconex[nr].push_back(G[x][i]);
biconex[nr].push_back(x);
}
min_time[x] = min(min_time[x], min_time[G[x][i]]);
}
else if (G[x][i] != f)
min_time[x] = min(min_time[x], min_time[G[x][i]]);
}
int main()
{
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);
}
tarjan(1, 0);
out << nr << "\n";
for (int i = 1; i <= nr; ++i)
{
for (int j = 0; j < biconex[i].size(); ++j)
out << biconex[i][j] << " ";
out << "\n";
}
return 0;
}