Pagini recente » Cod sursa (job #3143009) | Cod sursa (job #241895) | Cod sursa (job #1190888) | Cod sursa (job #1916137) | Cod sursa (job #3210137)
#include <fstream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
using namespace std;
ifstream cin("biconex.in");
ofstream cout("biconex.out");
const int NMAX = 1e5;
int n, m, indst, curentTime;
vector<int> G[NMAX + 1];
pair<int, int> st[NMAX + 1];
vector<vector<int>> GCC;
int DFSTime[NMAX + 1];
int low[NMAX + 1];
void GetBCC(int down, int up)
{
vector<int> C;
int curDown, curUp;
do
{
curDown = st[indst].first;
curUp = st[indst].second;
C.push_back(curDown);
C.push_back(curUp);
indst--;
}while(down != curDown || up != curUp);
sort(C.begin(), C.end());
C.erase(unique(C.begin(), C.end()), C.end());
GCC.push_back(C);
}
void DFS(int node, int dad)
{
DFSTime[node] = low[node] = ++curentTime;
for(int nextNode : G[node])
{
if(nextNode != dad && DFSTime[nextNode] < DFSTime[node])
st[++indst] = make_pair(nextNode, node);
if(!DFSTime[nextNode])
{
DFS(nextNode, node);
low[node] = min(low[node], low[nextNode]);
if(low[nextNode] >= DFSTime[node])
GetBCC(nextNode, node);
}
else
low[node] = min(low[node], DFSTime[nextNode]);
}
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= m; i++)
{
int a, b;
cin >> a >> b;
G[a].push_back(b);
G[b].push_back(a);
}
for(int i = 1; i <= n; i++)
if(!DFSTime[i])
DFS(i, 0);
cout << GCC.size() << '\n';
for(int i = 0; i < (int) GCC.size(); i++, cout << '\n')
for(int x : GCC[i])
cout << x << ' ';
return 0;
}