Pagini recente » Cod sursa (job #733075) | Cod sursa (job #68812) | Cod sursa (job #760924) | Cod sursa (job #3319734) | Cod sursa (job #3337787)
#include <bits/stdc++.h>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int n, m;
vector <int> adj[100001], adj2[100001];
queue <int> q;
vector <int> lista;
bool fr[100001];
map <int, vector <int> > mapa;
void dfs( int c )
{
fr[c] = 1;
for ( int i = 0; i < adj[c].size(); i ++ )
{
int l = adj[c][i];
if ( fr[l] == 0 )
{
dfs(l);
lista.push_back(l);
}
}
}
void append( int c, int root )
{
fr[c] = 1;
mapa[root].push_back(c);
for ( int i = 0; i < adj2[c].size(); i ++ )
{
int l = adj2[c][i];
if ( fr[l] == 0 )
append( l, root );
}
}
int main()
{
f >> n >> m;
for ( int i = 1; i <= m; i ++ )
{
int x, y;
f >> x >> y;
adj[x].push_back(y);
adj2[y].push_back(x);
}
dfs(1);
for ( int i = 1; i <= n; i ++ )
{
if( fr[i] == 0 )
lista.push_back(i);
fr[i] = 0;
}
for ( int i = lista.size() - 1; i >= 0; i -- )
if ( fr[lista[i]] == 0 )
append ( lista[i], lista[i] );
g << mapa.size() << '\n';
for ( auto it = mapa.begin(); it != mapa.end(); it ++ )
{
int idx = it -> first;
for ( int i = 0; i < mapa[idx].size(); i ++ )
g << mapa[idx][i] << " ";
g << '\n';
}
return 0;
}