Pagini recente » Cod sursa (job #2553853) | Cod sursa (job #3327255) | Cod sursa (job #3323613) | Cod sursa (job #1769280) | Cod sursa (job #1776372)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
struct nod
{
int viz=0;
vector <int> v;
vector <int> iv;
};
int n, m;
nod g[100001];
int comp[100001];
vector <int> a[100001];
int nc, k;
void dfs(int x)
{
g[x].viz=1;
for(int i=0; i<g[x].v.size(); i++)
if(g[g[x].v[i]].viz==0)
dfs(g[x].v[i]);
comp[++nc]=x;
}
void idfs(int x)
{
g[x].viz=-1;
a[k].push_back(x);
for(int i=0; i<g[x].iv.size(); i++)
if(g[g[x].iv[i]].viz==1)
idfs(g[x].iv[i]);
}
int main()
{
fin >> n >> m;
for(int i=1; i<=m; i++)
{
int x, y;
fin >> x >> y;
g[x].v.push_back(y);
g[y].iv.push_back(x);
}
for(int i=1; i<=n; i++)
{
if(g[i].viz==0)
dfs(i);
}
for(int i=n; i>=1; i--)
{
if(g[comp[i]].viz==1)
{
k++;
idfs(comp[i]);
}
}
fout << k << '\n';
for(int i=1; i<=k; i++)
{
for(int j=0; j<a[i].size(); j++)
fout << a[i][j] << " ";
fout << '\n';
}
return 0;
}
//#include <fstream>
//#include <vector>
//
//using namespace std;
//
//ifstream f("ctc.in");
//ofstream g("ctc.out");
//
//int n, m, i, K, x, y, j;
//vector <int> ls[100005], lsR[100005];
//vector <int> sol[100005];
//int viz[100005], care[100005], nc;
//
//void df_inainte(int x)
//{
// int i;
// viz[x] = 1;
// for (i = 0; i < ls[x].size(); i++)
// if (viz[ ls[x][i] ] == 0)
// df_inainte( ls[x][i] );
// care[++nc] = x;
//}
//
//void df_inapoi(int x)
//{
// int i;
// viz[x] = -1;
// sol[K].push_back(x);
// for (i = 0; i < lsR[x].size(); i++)
// if (viz[ lsR[x][i] ] == 1)
// df_inapoi( lsR[x][i] );
//}
//
//int main()
//{
// f >> n >> m;
// while (m)
// {
// f >> x >> y;
// ls[x].push_back(y);
// lsR[y].push_back(x);
// m--;
// }
//
// for (i = 1; i <= n; i++)
// if (viz[i] == 0)
// df_inainte(i);
//
// for (i = n; i >= 1; i--)
// if (viz[care[i]] != -1)
// {
// K++;
// df_inapoi(care[i]);
// }
//
// g << K << '\n';
// for (i = 1; i <= K; i++)
// {
// for (j = 0; j < sol[i].size(); j++)
// g << sol[i][j] << ' ';
// g << '\n';
// }
// return 0;
//}