Pagini recente » Cod sursa (job #701586) | Cod sursa (job #1420458) | Cod sursa (job #1406267) | Cod sursa (job #54505) | Cod sursa (job #1970778)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
using VI = vector<int>;
vector<VI> G;
int N, M;
vector<VI> ctc;
VI low, ind;
vector<bool> is;
int nr;
stack<int> st;
void Read();
void StronglyConnectedComponents();
void DFS( int nod );
void WriteComponents();
int main()
{
Read();
StronglyConnectedComponents();
WriteComponents();
fin.close();
fout.close();
return 0;
}
void Read()
{
int x, y;
fin >> N >> M;
G = vector<VI>(N + 1);
is = vector<bool>(N + 1);
low = ind = VI(N + 1);
while ( M-- )
{
fin >> x >> y;
G[x].push_back(y);
}
}
void StronglyConnectedComponents()
{
for ( int i = 1; i <= N; ++i )
if ( !ind[i] )
DFS(i);
}
void DFS( int nod )
{
ind[nod] = low[nod] = ++nr;
st.push(nod); is[nod] = true;
for ( const int& v : G[nod] )
{
if ( !ind[v] )
{
DFS(v);
low[nod] = min( low[nod], low[v] );
}
else
if ( is[v] )
low[nod] = min( low[nod], low[v] );
}
if ( ind[nod] == low[nod] )
{
VI c;
int x;
do
{
x = st.top(); st.pop(); is[x] = false;
c.push_back(x);
} while ( x != nod );
ctc.push_back(c);
}
}
void WriteComponents()
{
fout << ctc.size() << '\n';
for ( const auto& x : ctc )
{
for ( const int& y : x )
fout << y << ' ';
fout << '\n';
}
}