Pagini recente » Cod sursa (job #1434752) | Cod sursa (job #1097248) | Cod sursa (job #1999983) | Cod sursa (job #506966) | Cod sursa (job #2324656)
#include <bits/stdc++.h>
#define N 100005
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector <int> L[N];
vector <int> T[N];
vector <int> sol[N];
stack <int> st;
bitset <N> viz;
int n, m, nrcc;
void Read()
{
int i, j;
fin >> n >> m;
while(m--)
{
fin >> i >> j;
L[i].push_back(j);
T[j].push_back(i);
}
}
void DFS2(int nod)
{
viz[nod] = 1;
sol[nrcc].push_back(nod);
for(auto i : T[nod])
if(viz[i] == 0)
DFS2(i);
}
void DFS1(int nod)
{
viz[nod] = 1;
for(auto i : L[nod])
if(viz[i] == 0)
DFS1(i);
st.push(nod);
}
void CTC()
{
int i, k;
for(i = 1; i <= n; i++)
if(viz[i] == 0)
DFS1(i);
viz.reset();
while(!st.empty())
{
k = st.top();
st.pop();
if(viz[k] == 0)
{
nrcc++;
DFS2(k);
}
}
}
void Write()
{
int i;
fout << nrcc << "\n";
for(i = 1; i <= n; i++, fout << "\n")
for(auto j : sol[i])
fout << j << " ";
}
int main()
{
Read();
CTC();
Write();
return 0;
}