Pagini recente » Cod sursa (job #3173884) | Cod sursa (job #567983) | Cod sursa (job #791127) | Cod sursa (job #2414413) | Cod sursa (job #1365915)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <set>
using namespace std;
const int maxn = 100005;
int n, m, level[maxn], lowlink[maxn];
vector <int> g[maxn];
stack <pair<int, int> > st;
vector < set<int> > bcc;
inline void extractbcc(int x, int y) {
int tx, ty;
set <int> s;
do {
tx = st.top().first;
ty = st.top().second;
st.pop();
s.insert(tx);
s.insert(ty);
} while(x != tx || y != ty);
bcc.push_back(s);
}
inline void dfs(int node, int father) {
level[node] = lowlink[node] = level[father] + 1;
for(vector <int> :: iterator it = g[node].begin() ; it != g[node].end() ; ++ it) {
if(*it == father)
continue;
if(!level[*it]) {
st.push(make_pair(node, *it));
dfs(*it, node);
lowlink[node] = min(lowlink[node], lowlink[*it]);
if(lowlink[*it] >= level[node])
extractbcc(node, *it);
}
else
lowlink[node] = min(lowlink[node], level[*it]);
}
}
int main() {
ifstream fin("biconex.in");
ofstream fout("biconex.out");
fin >> n >> m;
for(int i = 1 ; i <= m ; ++ i) {
int x, y;
fin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
dfs(1, 0);
fout << bcc.size() << '\n';
for(vector <set<int> > :: iterator it = bcc.begin() ; it != bcc.end() ; ++ it, fout << '\n')
for(set<int> :: iterator i = it->begin() ; i != it->end() ; ++ i)
fout << *i << ' ';
}