Pagini recente » Monitorul de evaluare | Cod sursa (job #545926) | Borderou de evaluare (job #1427420) | Borderou de evaluare (job #956081) | Cod sursa (job #3348044)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin ("biconex.in");
ofstream fout ("biconex.out");
const int mxN = 1e5 + 1;
struct muchie{
int u, v;
};
bool operator!=(muchie a, muchie b){
return a.u != b.u || a.v != b.v;
}
int n, m;
vector<int> G[mxN], compBic[mxN];
int ord[mxN], low[mxN], ind = 0, noBic = 0;
stack<muchie> st;
void DFS(int nod, int parinte){
ord[nod] = ++ind;
low[nod] = ind;
for(int x : G[nod]){
if(!ord[x]){
st.push({nod, x});
DFS(x, nod);
low[nod] = min(low[nod], low[x]);
if(low[x] >= ord[nod]){
noBic++;
while(st.top() != (muchie){nod, x}){
muchie aux = st.top();
st.pop();
compBic[noBic].push_back(aux.u);
compBic[noBic].push_back(aux.v);
}
muchie aux = st.top();
st.pop();
compBic[noBic].push_back(aux.u);
compBic[noBic].push_back(aux.v);
sort(compBic[noBic].begin(), compBic[noBic].end());
compBic[noBic].erase(unique(compBic[noBic].begin(), compBic[noBic].end()), compBic[noBic].end());
}
}else if(parinte != x && ord[x] < ord[nod]){
st.push({x, nod});
low[nod] = min(low[nod], ord[x]);
}
}
}
int main(){
fin >> n >> m;
for(int i = 1; i <= m; i++){
int a, b;
fin >> a >> b;
G[a].push_back(b);
G[b].push_back(a);
}
for(int i = 1; i <= n; i++){
if(!ord[i])
DFS(i, 0);
}
fout << noBic << "\n";
for(int i = 1; i <= noBic; i++){
for(auto x : compBic[i])
fout << x << " ";
fout << "\n";
}
}