Pagini recente » Profil oana | Monitorul de evaluare | Diferente pentru home intre reviziile 902 si 267 | Cod sursa (job #709543) | Cod sursa (job #1790969)
#include <bits/stdc++.h>
using namespace std;
int N, M, nrBiconexe;
const int Nmax = 100005;
vector<vector<int> > G, bic;
bitset<Nmax> used, articulation;
stack<pair<int,int> > S;
int depth[Nmax], upperMost[Nmax];
void outputSolution()
{
cout << nrBiconexe << "\n";
for(int i = 1; i <= nrBiconexe; ++i) {
for(auto it : bic[i])
cout << it << " ";
cout << "\n";
}
}
void output(int k)
{
++nrBiconexe;
while(true) {
auto crt = S.top();
S.pop();
bic[nrBiconexe].push_back(crt.second);
if(crt.first == k)
break;
}
bic[nrBiconexe].push_back(k);
}
void DFS(int k, int dad)
{
used[k] = true;
depth[k] = depth[dad] + 1;
upperMost[k] = depth[k];
for(auto it : G[k])
if(!used[it]) {
S.push({k, it});
DFS(it, k);
upperMost[k] = min(upperMost[k], upperMost[it]);
if(upperMost[it] >= depth[k]) /// it is disconected here.
{
articulation[k] = true;
output(k);
}
}
else
if(it != dad && depth[it] < upperMost[k])
upperMost[k] = depth[it];
}
int main()
{
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
cin.sync_with_stdio(false);
cin >> N >> M;
G.resize(N + 1); bic.resize(N + 1);
for(int i = 1; i <= M; ++i) {
int x, y;
cin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
for(int i = 1; i <= N; ++i)
if(!used[i])
DFS(i, 0);
outputSolution();
return 0;
}