Pagini recente » Cod sursa (job #2675009) | Cod sursa (job #2063771) | Cod sursa (job #2955567) | Cod sursa (job #2446496) | Cod sursa (job #2922953)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
const int MAXN=200010;
stack <int> st;
vector <int> g[MAXN],gt[MAXN],componenta[MAXN];
bool visitp[MAXN],visitfin[MAXN];
int n,m,rez;
void dfs (int nod){
visitp[nod]=1;
for (int i=0;i<g[nod].size ();++i){
if (visitp[g[nod][i]]==0)
dfs (g[nod][i]);
}
st.push (nod);
}
void dfs2 (int nod){
visitfin[nod]=1;
componenta[rez].push_back (nod);
for (int i=0;i<gt[nod].size ();++i){
if (visitp[gt[nod][i]]==1 and visitfin[gt[nod][i]]==0){
dfs2 (gt[nod][i]);
}
}
}
void solve (int radacina){
dfs (radacina);
while (st.empty ()==false){
rez++;
dfs2 (st.top ());
while (st.empty ()==false and visitfin[st.top ()]==1)
st.pop ();
}
}
int main()
{
fin >>n>>m;
for (int i=1;i<=m;++i){
int x,y;
fin >>x>>y;
g[x].push_back (y);
gt[y].push_back (x);
}
for (int i=1;i<=n;++i){
if (visitfin[i]==0){
solve (i);
}
}
fout <<rez<<'\n';
for (int i=1;i<=rez;++i){
for (int j=0;j<componenta[i].size ();++j){
fout <<componenta[i][j]<<' ';
}
fout <<'\n';
}
fin.close ();
fout.close ();
return 0;
}