Pagini recente » Cod sursa (job #981542) | Cod sursa (job #1087244) | Cod sursa (job #1862823) | Cod sursa (job #2522741) | Cod sursa (job #3339165)
#include <bits/stdc++.h>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
const int nmax=1e5+5;
int n,m,comp[nmax];
vector <int> gr1[nmax],gr2[nmax],rez[nmax];
stack <int> st;
bool viz[nmax];
void dfs1(int nod)
{
viz[nod]=true;
for (int vec:gr1[nod] )
if ( !viz[vec] )
dfs1(vec);
st.push(nod);
}
void dfs2(int nod, int cnx)
{
comp[nod]=cnx;
for (int vec:gr2[nod] )
if ( comp[vec]==-1 )
dfs2(vec,cnx);
}
int main()
{
f >> n >> m;
for (int i=1; i<=m; i++ )
{
int x,y; f >> x >> y;
gr1[x].push_back(y);
gr2[y].push_back(x);
}
for (int i=1; i<=n; i++ )
if ( !viz[i] )
dfs1(i);
for (int i=1; i<=n; i++ )
comp[i]=-1;
int cnx=0;
while ( !st.empty() )
{
int x=st.top(); st.pop();
if ( comp[x]==-1 )
dfs2(x,cnx++);
}
g << cnx << '\n';
for (int i=1; i<=n; i++ )
rez[comp[i]].push_back(i);
for (int i=0; i<cnx; i++, g << '\n' )
for (auto j:rez[i] )
g << j << " ";
return 0;
}