Pagini recente » Cod sursa (job #2324385) | Cod sursa (job #1071657) | Cod sursa (job #1174888) | Cod sursa (job #1582296) | Cod sursa (job #2801696)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
const int nmax = 1e5 + 5;
int n, m;
bool vis[nmax];
vector <int> adj[nmax], disc_time, lowest_anc;
stack < pair<int,int> > st;
vector <vector<int> > comp;
void read(){
fin >> n >> m;
for(int i = 1; i <= m; i++){
int x, y;
fin >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}
disc_time.assign(n + 1, -1);
lowest_anc.resize(n + 1);
}
void biconnected_comp(int parent, int node){
vector <int> c;
int x, y;
do {
x = st.top().first, y = st.top().second;
st.pop();
c.push_back(x);
c.push_back(y);
} while(x != parent || y != node);
comp.push_back(c);
}
void dfs(int node, int parent, int discTime){
disc_time[node] = lowest_anc[node] = discTime;
for(vector <int>::iterator it = adj[node].begin(); it != adj[node].end(); it++){
if(*it == parent)
continue;
if(disc_time[*it] == -1){
st.push({node, *it});
dfs(*it, node, discTime + 1);
lowest_anc[node] = min(lowest_anc[node], lowest_anc[*it]);
if(lowest_anc[*it] >= disc_time[node])
biconnected_comp(node, *it);
} else
lowest_anc[node] = min(lowest_anc[node], disc_time[*it]);
}
}
void print_ans(){
fout << comp.size() << "\n";
for(int i = 0; i < comp.size(); i++){
memset(vis, 0, sizeof(vis));
//sort(comp[i].begin(), comp[i].end());
//comp[i].erase(unique(comp[i].begin(), comp[i].end()), comp[i].end());
for(int j = 0; j < comp[i].size(); j++)
if(!vis[comp[i][j]]){
fout << comp[i][j] << " ";
vis[comp[i][j]] = 1;
}
fout << "\n";
}
}
int main()
{
read();
dfs(1, 0, 0);
print_ans();
return 0;
}