Pagini recente » Cod sursa (job #290347) | Cod sursa (job #566185) | Cod sursa (job #579413) | Cod sursa (job #2042628) | Cod sursa (job #1923084)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
#define MaxN 100009
int n, m, ap[MaxN], nr;
bool viz[MaxN];
vector<int> G[MaxN], G_rev[MaxN], Ans[MaxN];
stack<int> st;
void Df(int i) {
viz[i] = 1;
for ( const auto x : G[i] )
if ( !viz[x] )
Df(x);
st.push(i);
}
void Df2(int i) {
ap[i] = nr;
for ( const auto x : G_rev[i] )
if ( ap[x] == -1 )
Df2(x);
}
int main() {
fin >> n >> m;
for ( int i = 1, x, y; i <= m; ++i ) {
fin >> x >> y;
G[x].push_back(y);
G_rev[y].push_back(x);
}
for ( int i = 1; i <= n; ++i )
if ( !viz[i] )
Df(i);
for ( int i = 1; i <= n; ++i ) {
viz[i] = 0;
ap[i] = -1;
}
while(!st.empty()){
int x = st.top();
if ( ap[x] == -1 ) {
nr++;
Df2(x);
}
st.pop();
}
for ( int i = 1; i <= n; ++i )
Ans[ap[i]].push_back(i);
fout << nr << '\n';
for ( int i = 1; i <= n; ++ i ) {
for ( const auto y : Ans[i] )
fout << y << ' ';
fout << '\n';
}
}