Pagini recente » Cod sursa (job #2973630) | Cod sursa (job #2403744) | Cod sursa (job #1373456) | Cod sursa (job #2435141) | Cod sursa (job #1378769)
///BICONNECTED COMPONENTS
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <stack>
#include <algorithm> ///sort, unique
using namespace std;
typedef pair<int, int> Pair;
list<vector<int> > answ;
void bicon(vector<vector<int> >& adjList, vector<Pair>& nds,
int v, int pV, int ind, stack<Pair>& s) {
nds[v].first = nds[v].second = ind;
++ind;
for(auto i=adjList[v].begin(); i!=adjList[v].end(); ++i) {
if(*i == pV) continue;
if(nds[*i].first == -1) {
s.push(Pair(v, *i));
bicon(adjList, nds, *i, v, ind, s);
nds[v].second = min(nds[v].second, nds[*i].second);
if(nds[*i].second >= nds[v].first) {
auto comp = vector<int>();
int c1, c2;
do {
c1 = s.top().first;
c2 = s.top().second;
s.pop();
comp.push_back(c1);
comp.push_back(c2);
} while(c1 != v || c2 != *i);
sort(comp.begin(), comp.end());
comp.erase(unique(comp.begin(), comp.end()), comp.end());
answ.push_back(comp);
}
} else nds[v].second = min(nds[v].second, nds[*i].first);
}
}
int main() {
ifstream inStr("biconex.in");
ofstream outStr("biconex.out");
int N, M;
inStr >> N >> M;
vector<vector<int> > adjList(N);
int from, to;
for(int i=0; i<M; ++i) {
inStr >> from >> to;
adjList[--from].push_back(--to);
adjList[to].push_back(from);
}
stack<Pair> s;
vector<Pair> nds(N, Pair(-1, 0));
int ind = 0;
bicon(adjList, nds, 0, -1, ind, s);
outStr << answ.size() << '\n';
for(auto comp:answ) {
for(auto i=comp.begin(); i!=comp.end(); ++i)
outStr << *i + 1 << ' ';
outStr << '\n';
}
return 0;
}