Pagini recente » Istoria paginii runda/simulare_radu/clasament | Istoria paginii runda/uvs_training_1/clasament | Autentificare | Istoria paginii runda/test912/clasament | Cod sursa (job #2012425)
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
int i, n, a, b, fv[100005], mi[100005], ctc, nr, m, j, scs[100005];
vector < int > gf[100005], rsp[100005];
stack < int > st;
int dfs ( int nod )
{
nr++;
fv[nod] = nr;
mi[nod] = nr;
st.push(nod);
for ( int i = 0 ; i < gf[nod].size() ; i++ )
{
if ( fv [ gf[nod][i] ] == 0)
dfs( gf[nod][i] );
if ( scs[gf[nod][i]] == 0 )
mi[nod] = min ( mi[nod], mi[ gf[nod][i] ] );
}
if ( mi[nod] == fv[nod] )
{
ctc++;
while ( st.top() != nod )
{
scs[st.top()] = 1;
rsp[ctc].push_back(st.top());
st.pop();
}
scs[st.top()] = 1;
rsp[ctc].push_back(st.top());
st.pop();
}
return mi[nod];
}
int main ()
{
fin>>n>>m;
for ( i = 1; i <= m ; i++ )
{
fin>>a>>b;
gf[a].push_back(b);
}
for ( i = 1; i <= n ; i++ )
{
nr = 0;
if ( fv[i] == 0 )
dfs(i);
}
fout<<ctc<<'\n';
for ( i = 1 ; i <= ctc ; i++ )
{
for ( j = 0 ; j < rsp[i].size() ; j++ )
{
fout<<rsp[i][j]<<" ";
}
fout<<'\n';
}
return 0;
}