Pagini recente » Cod sursa (job #18734) | Cod sursa (job #1078921) | Cod sursa (job #240343) | Cod sursa (job #859326) | Cod sursa (job #1313830)
#include<fstream>
#include<vector>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
const int nmax = 100006;
int n, m, st[nmax], nrcomp, lst;
vector < int > vecini[nmax], antivec[nmax], v[nmax];
bool poz[nmax];
void top_sort(int nod)
{
poz[nod] = 1;
for(int i = 0; i<vecini[nod].size(); i++)
if(!poz[vecini[nod][i]])
top_sort(vecini[nod][i]);
st[++lst] = nod;
}
void dfs(int nod)
{
poz[nod] = 0;
v[nrcomp].push_back(nod);
for(int i = 0; i<antivec[nod].size(); i++)
if(poz[antivec[nod][i]])
dfs(antivec[nod][i]);
}
int main()
{
int player_unu=0;
in>>n>>m;
for(int i = 1; i<=m; i++)
{
int x,y;
in>>x>>y;
vecini[x].push_back(y);
antivec[y].push_back(x);
}
for(int i = 1; i<=n; i++)
if(!poz[i])
top_sort(i);
for(int i = n; i>0; i--)
{
if(poz[st[i]])
{
++nrcomp;
dfs(st[i]);
}
}
out<<nrcomp<<'\n';
for(int i = 1; i<=nrcomp; i++)
{
for(int j = 0; j<v[i].size(); j++)
out<<v[i][j]<<' ';
out<<'\n';
}
return player_unu;
}