Pagini recente » Cod sursa (job #1494955) | Cod sursa (job #1746477) | Cod sursa (job #3275217) | Cod sursa (job #2976355) | Cod sursa (job #2107412)
#include <bits/stdc++.h>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
const int NMAX = 100000;
vector<vector<int>> ctc;
vector<pair<int,int>> G[NMAX+2], GP[NMAX+2];
vector<int> order;
bool viz[NMAX+2];
int comp[NMAX+2], profit[NMAX+2], c_ind = 0;
vector<pair<int,int>> NG[NMAX+2];
int N, M;
void Dfs_Plus(int nod)
{
viz[nod] = 1;
for( auto e: G[nod] ) {
int x = e.first;
if( viz[x] ) continue;
Dfs_Plus(x);
}
order.push_back(nod);
}
void Dfs_Minus(int nod)
{
comp[nod] = c_ind;
viz[nod] = 1;
ctc.back().push_back(nod);
for( auto e : GP[nod] ) {
int x = e.first;
if( viz[x] ) continue;
Dfs_Minus(x);
}
}
int main()
{
in >> N >> M;
for( int i = 1; i <= M; ++i ) {
int x,y,w;
in >> x >> y;
w = 0;
G[x].push_back({y,w});
GP[y].push_back({x,w});
}
for( int i = 1; i <= N; ++i ) {
if( viz[i] ) continue;
Dfs_Plus(i);
}
memset(viz, 0, sizeof(viz));
reverse(order.begin(), order.end());
for( auto x : order ) {
if( viz[x] ) continue;
++c_ind;
ctc.push_back(vector<int>());
Dfs_Minus(x);
}
///for( int i = 1; i <= N; ++i ) cout << comp[i] << ' ';
out << ctc.size() << '\n';
for( auto ln : ctc ) {
for( auto x : ln ) out << x << ' ';
out << '\n';
}
return 0;
}