Pagini recente » Cod sursa (job #1617595) | Cod sursa (job #672089) | Cod sursa (job #577527) | Cod sursa (job #1924976) | Cod sursa (job #943530)
Cod sursa(job #943530)
#include<fstream>
#include<vector>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int MAXN = 200010;
int N, M, x, y, fiu, nod, u, s[MAXN], h1, h2;
bool used[MAXN];
vector <int> G[MAXN], F[MAXN], sol[MAXN];
void DFS_suc(int nod){
int i;
used[nod] = 1;
for(i=0; i<G[nod].size(); ++i)
{
y = G[nod][i];
if(used[y] == 0)
DFS_suc(y);
}
s[++h1] = nod;
}
void DFS_pred(int nod){
int i;
used[nod] = 1;
for(i=0; i<F[nod].size(); ++i)
{
y = F[nod][i];
if(used[y] == 0)
DFS_pred(y);
}
sol[h2].push_back(nod);
}
int main(){
int i, j;
fin >> N >> M;
for(i=0; i<M; ++i){
fin >> nod >> fiu;
G[nod].push_back(fiu);
F[fiu].push_back(nod);
}
for(i=1; i<=N; ++i)
if(!used[i])
DFS_suc(i);
for(i=1; i<=N; ++i)
used[i] = 0;
for(i=N; i>0; --i)
if(!used[s[i]]){
++h2;
DFS_pred(s[i]);
}
fout << h2 << "\n";
for(i=1; i<=h2; ++i){
for(j=0; j<sol[i].size(); ++j)
fout << sol[i][j] << " ";
fout << "\n";
}
fin.close();
fout.close();
return 0;
}