Pagini recente » Cod sursa (job #2305873) | Cod sursa (job #3248360) | Cod sursa (job #2986369) | Cod sursa (job #1735885) | Cod sursa (job #2199341)
#include <bits/stdc++.h>
#define dimn 100005
#define mp std::make_pair
using data = std::pair <int, int>;
std::ifstream f("biconex.in");
std::ofstream g("biconex.out");
int N;
std::vector <int> comp[dimn];
std::list <int> adj[dimn];
std::stack <data> s;
int ord[dimn], lowlink[dimn];
int nrb;
int lvl = 1;
void dfs(int start=1) {
ord[start] = lowlink[start] = lvl++;
for (auto vec:adj[start]) {
if(!ord[vec]) {
s.push(mp(start, vec));
dfs(vec);
lowlink[start] = std::min(lowlink[start], lowlink[vec]);
if(lowlink[vec] >= ord[start]) {
nrb++;
while(s.top().first != start)
comp[nrb].push_back(s.top().second),
s.pop();
comp[nrb].push_back(s.top().first);
comp[nrb].push_back(s.top().second);
s.pop();
std::sort(comp[nrb].begin(), comp[nrb].end());
}
}
else
lowlink[start] = std::min(lowlink[start], ord[vec]);
}
}
void citire() {
f >> N;
int M; f >> M;
for (int i=0, y, x; i<M; i++) {
f >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}
}
void rezolvare() {
for (int i=1; i<=N; i++)
if(!ord[i])
dfs(i);
g << nrb << "\n";
for (int i=1, j; i<=nrb; i++) {
for (j=0; j<comp[i].size(); j++)
g << comp[i][j] << " ";
g << "\n";
}
}
int main()
{
citire();
rezolvare();
return 0;
}