Pagini recente » Cod sursa (job #1924743) | Cod sursa (job #1055969) | Cod sursa (job #2519943) | Cod sursa (job #461497) | Cod sursa (job #1621748)
#include <fstream>
#include <bitset>
#include <vector>
#include <queue>
#include <set>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int low[100010], niv[100010], N, M, x, y, nr;
pair<int ,int> a;
vector<int>L[100010];
set<int> SOL[200100];
set<int>::iterator it;
bitset<100010>v, X;
deque<pair<int, int> >Q;
void dfs(int node, int nivel, int tata)
{
v[node] = 1;
Q.push_back(make_pair(tata, node));
low[node] = niv[node] = nivel;
for(int i = 0; i < L[node].size(); i ++)
{
if(L[node][i] == tata)
continue;
if(v[ L[node][i] ] == 0)
{
dfs(L[node][i], nivel + 1, node);
low[node] = min(low[node], low[ L[node][i] ]);
if(low[ L[node][i] ] >= niv[node])
{
nr ++;
do{
a = Q.back();
SOL[nr].insert(a.first);
SOL[nr].insert(a.second);
Q.pop_back();
}while(a.first != node && a.second != L[node][i]);
}
}
else
{
low[node] = min(low[node], low[ L[node][i] ]);
}
}
}
int main()
{
fin >> N >> M;
for(int i = 1; i <= M; i ++)
{
fin >> x >> y;
L[x].push_back(y);
}
dfs(1, 1, 0);
fout << nr << '\n';
for(int i = 1; i <= nr; i ++)
{
for(it = SOL[i].begin(); it != SOL[i].end(); it ++)
{
fout << *it << " ";
}
fout << '\n';
}
return 0;
}