Pagini recente » Cod sursa (job #2470062) | Cod sursa (job #1707255) | Cod sursa (job #1110950) | Istoria paginii runda/ooo | Cod sursa (job #1519692)
#include <fstream>
#include <vector>
#include <stack>
#include <bitset>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int Inf = 0x3f3f3f3f;
int n, m;
int nv;
vector<vector<int> > G, C;
vector<int> niv, L, c;
vector<bool> inS;
stack<int> st;
void Read();
void Tarjan(int nod);
int main()
{
Read();
for ( int i = 1; i <= n; ++i )
if ( niv[i] == 0 )
nv = 0, Tarjan(i);
fout << C.size() << "\n";
for (const auto& c : C)
{
for (const auto& x : c)
fout << x << ' ';
fout << '\n';
}
fin.close();
fout.close();
return 0;
}
void Read()
{
fin >> n >> m;
int x, y;
G = vector<vector<int>>(n + 1);
niv = L = vector<int>(n + 1);
inS = vector<bool>(n + 1);
for ( int i = 1; i <= m; ++i )
{
fin >> x >> y;
G[x].push_back(y);
}
}
void Tarjan(int x)
{
niv[x] = L[x] = ++nv;
st.push(x);
inS[x] = true;
for ( const auto& y : G[x] )
if ( niv[y] == 0 )
{
Tarjan(y);
L[x] = min(L[x], L[y]);
}
else
if ( inS[y] )
L[x] = min(L[x], niv[y]);
if ( niv[x] == L[x] )
{
c.clear();
int x2;
while ( true )
{
c.push_back(x2 = st.top());
st.pop();
inS[x2] = false;
if ( x2 == x )
break;
}
C.push_back(c);
}
}