Pagini recente » Cod sursa (job #2268004) | Cod sursa (job #3181186) | Cod sursa (job #328996) | Cod sursa (job #1077217) | Cod sursa (job #2127338)
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
using namespace std;
fstream fin("ctc.in", ios::in), fout("ctc.out", ios::out);
vector<vector<int> > G, GT;
int n , m , contor , nrs;
vector<bool> V;
vector<int> S, R;
void read()
{
fin >> n >> m;
G = GT = vector<vector<int>>(n + 1);
V = vector<bool> (n + 1, false);
R = vector<int> (n + 1 , 0);
for(int i = 1 ; i <= m ; i++)
{
int a , b;
fin >> a >> b;
G[a].push_back(b);
GT[b].push_back(a);
}
}
void dfs(int k)
{
V[k] = true;
for(auto x : G[k])
if(!V[x])
dfs(x);
S.push_back(k);
}
void dfsGT(int k, int root)
{
R[k] = root;
V[k]=1;
for(auto x: GT[k])
if(! V[x])
dfsGT(x, root);
}
int main()
{
read();
for(int i = 1 ; i <= n ; i ++)
if(! V[i])
dfs(i);
V = vector<bool> (n + 1, false);
for(vector<int>::reverse_iterator it = S.rbegin() ; it != S.rend() ; it ++)
if(!V[*it]) {
dfsGT(* it, * it);
}
vector<vector<int>> C;
vector<int> P = vector<int> (n + 1, 0);
for(int i = 1 ; i <= n ; i ++)
if(P[R[i]] == 0)
{
C.push_back(vector<int>(0));
C.back().push_back(i);
P[R[i]] = C.size();
}
else
C[P[R[i]]-1].push_back(i);
fout << C.size() << "\n";
for(auto M : C)
{
for(auto x : M)
fout << x << " ";
fout << "\n";
}
return 0;
}