Pagini recente » Cod sursa (job #2379927) | Cod sursa (job #2036298) | Cod sursa (job #2931024) | Cod sursa (job #6668) | Cod sursa (job #2610756)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream cin("biconex.in");
ofstream cout("biconex.out");
const int NMAX = 1e5;
int N, M;
vector <int> g[NMAX + 2];
bool seen[NMAX + 2];
int timee[NMAX + 2], lowTime[NMAX + 2];
stack <int> st;
int nrBix;
vector <int> bix[NMAX + 2];
void dfs(int node, int dady)
{
timee[node] = lowTime[node] = timee[dady] + 1;
st.push(node);
for(auto it : g[node])
if(it == dady) continue;
else
{
if(timee[it])
{
lowTime[node] = min(lowTime[node], timee[it]);
continue;
}
dfs(it, node);
lowTime[node] = min(lowTime[node], lowTime[it]);
if(timee[node] <= lowTime[it]) ///node punct de articulatie
{
++nrBix;
int k;
do
{
k = st.top(); st.pop();
bix[nrBix].push_back(k);
}
while(k != it);
bix[nrBix].push_back(node);
}
}
}
int main()
{
cin >> N >> M;
for(int i = 1; i <= M; i++)
{
int x, y;
cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
for(int i = 1; i <= N; i++)
if(!timee[i]) dfs(i, 0);
cout << nrBix << '\n';
for(int i = 1; i <= nrBix; i++)
{
for(auto it : bix[i])
cout << it << ' ';
cout << '\n';
}
return 0;
}