Pagini recente » Cod sursa (job #3293330) | Cod sursa (job #3292991) | Cod sursa (job #3291454) | clasament-arhiva-educationala | Cod sursa (job #3286762)
#include <bits/stdc++.h>
#define NMAX 100001
using namespace std;
vector <int> aux;
vector <vector<int>> ctc;
vector <vector<int>> a(NMAX);
vector <vector<int>> ar(NMAX);
vector <int> ord;
int rez=0;
vector <int>frecv(NMAX);
vector <int>frecv0(NMAX);
void dfs1(int nod)
{ frecv[nod]=1;
for(int i=0; i<a[nod].size(); i++)
{
if(frecv[a[nod][i]]==0)
{
frecv[a[nod][i]]=1;
dfs1(a[nod][i]);
}
}
ord.push_back(nod);
}
void dfs2(int nod)
{
for(int j=0; j<ar[nod].size(); j++)
{
if(frecv0[ar[nod][j]]==0)
{
frecv0[ar[nod][j]]=1;
dfs2(ar[nod][j]);
}
}
aux.push_back(nod);
}
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int main()
{
int n,m;
fin>>n>>m;
for(int u,v,i=1; i<=m; i++)
{
fin>>u>>v;
a[u].push_back(v);
ar[v].push_back(u);
}
for (int i=1; i<=n; i++)
{
if(frecv[i]==1)
continue;
frecv[i]=1;
dfs1(i);
}
frecv.clear();
for(int i=ord.size()-1; i>=0; i--)
{
if(frecv0[ord[i]]==1)
continue;
frecv0[ord[i]]=1;
dfs2(ord[i]);
rez++;
ctc.push_back(aux);
aux.clear();
}
rez--;
fout<<rez+1<<'\n';
for(int i=0; i<=rez; i++)
{
for(int j=0; j<ctc[i].size(); j++)
{
fout<<ctc[i][j]<<" ";
}
fout<<'\n';
}
return 0;
}