Pagini recente » Cod sursa (job #1618984) | Cod sursa (job #1574938) | Cod sursa (job #2106720) | Cod sursa (job #2564331) | Cod sursa (job #2686472)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
int n, m, i, j, ord[100005], niv_min[100005];
bool viz[100005];
vector<int> v[100005], t(100005, -1);
vector<vector<int> > comp;
stack<int> st;
void dfs(int nod) {
int it, x;
vector<int> c;
viz[nod] = true;
ord[nod] = ord[t[nod]] + 1;
niv_min[nod] = ord[nod];
st.push(nod);
for(it = 0; it < v[nod].size(); it++)
if(viz[v[nod][it]]) {
if(v[nod][it] != t[nod])
niv_min[nod] = min(niv_min[nod], ord[v[nod][it]]);
}
else {
t[v[nod][it]] = nod;
dfs(v[nod][it]);
niv_min[nod] = min(niv_min[nod], niv_min[v[nod][it]]);
if(ord[nod] <= niv_min[v[nod][it]]) {
c.clear();
while(!st.empty()) {
x = st.top();
st.pop();
c.push_back(x);
if(x == v[nod][it]) {
c.push_back(nod);
comp.push_back(c);
break;
}
}
}
}
}
int main() {
ifstream f("biconex.in");
ofstream g("biconex.out");
f >> n >> m;
while(m) {
f >> i >> j;
v[i].push_back(j);
v[j].push_back(i);
m--;
}
for(i = 1; i <= n; i++)
if(!ord[i]) {
t[i] = 0;
dfs(i);
}
g << comp.size() << '\n';
for(i = 0; i < comp.size(); i++, g << '\n')
for(j = 0; j < comp[i].size(); j++)
g << comp[i][j] << ' ';
return 0;
}