Pagini recente » Monitorul de evaluare | Cod sursa (job #1173239) | Cod sursa (job #2295147) | Cod sursa (job #640978) | Cod sursa (job #3037958)
#include <fstream>
#include <stack>
#include <set>
#include <vector>
using namespace std;
ifstream cin("biconex.in");
ofstream cout("biconex.out");
const int nmax = 1e5 + 5;
vector <int> edge[nmax];
int cate[nmax], disc[nmax], low[nmax], vis[nmax], compnod[nmax], comp[nmax], compmuchii[nmax], parent[nmax];
int id, cnt;
set <int> s[nmax];
stack <pair<int, int>> st;
bool ok = true;
void check(int node)
{
vis[node] = 1;
for(int i = 0; i < edge[node].size(); i++)
if(!vis[edge[node][i]])
check(edge[node][i]);
}
void dfs(int node)
{
disc[node] = low[node] = ++cnt;
int cnt1 = 0;
for(int i = 0; i < edge[node].size(); i++){
int child = edge[node][i];
if(disc[child] == 0){
cnt1++;
st.push({node, child});
parent[child] = node;
dfs(child);
low[node] = min(low[child], low[node]);
if((node == 1 and cnt1 > 1) or (node != 1 and low[child] >= disc[node])){
id++;
while(st.top().first != node and st.top().second != child){
/*if(comp[st.top().first] != id){
cate[st.top().first]++;
compnod[id]++;
compmuchii[id]++;
}
if(comp[st.top().second] != id){
cate[st.top().second]++;
compnod[id]++;
compmuchii[id]++;
}
comp[st.top().first] = id;
comp[st.top().second] = id;
if(cate[st.top().first] > 2 or cate[st.top().second] > 2)
ok = false;*/
//cout << st.top().first << " " << st.top().second << "\n";
s[id].insert(st.top().first);
s[id].insert(st.top().second);
st.pop();
}
/*if(comp[st.top().first] != id){
cate[st.top().first]++;
compnod[id]++;
compmuchii[id]++;
}
if(comp[st.top().second] != id){
cate[st.top().second]++;
compnod[id]++;
compmuchii[id]++;
}
comp[st.top().first] = id;
comp[st.top().second] = id;
if(cate[st.top().first] > 2 or cate[st.top().second] > 2)
ok = false;*/
//cout << st.top().first << " " << st.top().second << "\n";
s[id].insert(st.top().first);
s[id].insert(st.top().second);
st.pop();
}
}
else if(child != parent[node]){
low[node] = min(low[node], disc[child]);
if(disc[node] > disc[child])
st.push({node, child});
}
}
}
int main()
{
//int t;
//cin >> t;
int t = 1;
while(t--){
int n, m;
cin >> n >> m;
for(int i = 1; i <= m; i++){
int x, y;
cin >> x >> y;
edge[x].push_back(y);
edge[y].push_back(x);
}
check(1);
for(int i = 1; i <= n; i++)
if(!vis[i])
ok = false;
for(int i = 1; i <= n; i++){
if(disc[i] == 0)
dfs(i);
if(!st.empty()){
id++;
while(!st.empty()){
/*if(comp[st.top().first] != id){
cate[st.top().first]++;
compnod[id]++;
compmuchii[id]++;
}
if(comp[st.top().second] != id){
cate[st.top().second]++;
compnod[id]++;
compmuchii[id]++;
}
comp[st.top().first] = id;
comp[st.top().second] = id;
if(cate[st.top().first] > 2 or cate[st.top().second] > 2)
ok = false;*/
//cout << st.top().first << " " << st.top().second << "\n";
s[id].insert(st.top().first);
s[id].insert(st.top().second);
st.pop();
}
}
}
cout << id << "\n";
for(int i = 1; i <= id; i++){
for(auto it = s[i].begin(); it != s[i].end(); it++)
cout << *(it) << " ";
cout << "\n";
}
/*for(int i = 1; i <= id; i++){
if(compnod[i] * (compnod[i] - 1) / 2 != compmuchii[i])
ok = false;
}
if(!ok)
cout << "NU\n";
else{
cout << "DA\n";
}
for(int i = 1; i <= n; i++){
disc[i] = low[i] = compnod[i] = compmuchii[i] = parent[i] = cate[i] = comp[i] = vis[i] = 0;
edge[i].clear();
}*/
}
return 0;
}