Pagini recente » Cod sursa (job #499189) | Cod sursa (job #2777161) | Istoria paginii info-oltenia-2018/echipe/clasament/5-6 | Cod sursa (job #1105189) | Cod sursa (job #3212326)
#include <bits/stdc++.h>
#include <unordered_map>
#define nmax 100005
#define kmax 200005
#define MOD 1999999973
#define INF 2012345678
#define ll long long
using namespace std;
//#define fin cin
//#define fout cout
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, nrCT;
vector <int> L[nmax], T[nmax];
bitset <nmax> viz;
int sol[nmax], lg;
int ct[nmax];
void DFSLex(int k)
{
viz[k] = 1;
for (int i : L[k])
if (viz[i] == 0)
DFSLex(i);
sol[++lg] = k;
}
void SortTop()
{
for (int i = 1; i <= n; i++)
if (viz[i] == 0)
DFSLex(i);
}
void DFS(int k)
{
viz[k] = 1;
for (int i : T[k])
if (viz[i] == 0)
DFS(i);
}
void Kosaraju()
{
int k;
viz.reset();
for (int i = n; i >= 1; i--)
{
k = sol[i];
if (viz[k] == 0)
{
DFS(k);
nrCT++;
}
ct[k] = nrCT;
}
}
int main()
{
int i, j, x, y;
fin >> n >> m;
for (i = 1; i <= m; i++)
{
fin >> x >> y;
L[x].push_back(y);
T[y].push_back(x);
}
SortTop();
Kosaraju();
fout << nrCT << "\n";
for (i = 1; i <= nrCT; i++, fout << "\n")
for (j = 1; j <= n; j++)
if (ct[j] == i)
fout << j << " ";
fin.close();
fout.close();
return 0;
}