Pagini recente » Cod sursa (job #424198) | Cod sursa (job #967405) | Cod sursa (job #1442833) | Cod sursa (job #224192) | Cod sursa (job #1784803)
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
vector<int> G[100010],biconex[1000010],stk;
int N, M, viz[100010], 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]])
{
time[G[x][i]] = min_time[G[x][i]] = ++tm;
tarjan(G[x][i],x);
if (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;
}