Pagini recente » Rezultatele filtrării | Cod sursa (job #939022) | Rezultatele filtrării | Rezultatele filtrării | Cod sursa (job #2168110)
#include<bits/stdc++.h>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int N,M,x,y,nr,Minus[100001];
bool Plus[100001];
vector <int> G[100001],GT[100001],ctc[100001];
stack <int> st;
void DFS1(int nod){
Plus[nod]=1;
for(int i=0;i<G[nod].size();++i)
if(!Plus[G[nod][i]])
DFS1(G[nod][i]);
st.push(nod);
}
void DFS2(int nod){
Minus[nod]=nr;
for(int i=0;i<GT[nod].size();++i)
if(!Minus[GT[nod][i]])
DFS2(GT[nod][i]);
}
int main()
{
f>>N>>M;
while(M--){
f>>x>>y;
G[x].push_back(y);
GT[y].push_back(x);
}
for(int i=1;i<=N;++i)
if(!Plus[i])
DFS1(i);
while(!st.empty()){
x=st.top();
st.pop();
if(!Minus[x]){
++nr;
DFS2(x);
}
}
for(int i=1;i<=N;++i)
ctc[Minus[i]].push_back(i);
g<<nr<<'\n';
for(int i=1;i<=nr;++i){
for(int j=0;j<ctc[i].size();++j)g<<ctc[i][j]<<' ';
g<<'\n';
}
return 0;
}