Pagini recente » Cod sursa (job #3227344) | Cod sursa (job #2548895) | Cod sursa (job #1270645) | Cod sursa (job #1856135) | Cod sursa (job #639836)
Cod sursa(job #639836)
#include <fstream>
#include <vector>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
const int max_n=100005;
int n,m;
vector <int> grafn[max_n],graftrans[max_n],con[max_n];
int st[max_n],k=1;
bool viz[max_n];
void dfnormal(int nod)
{
viz[nod]=1;
for(int i=0;i<grafn[nod].size();i++)
if(!viz[grafn[nod][i]]) dfnormal(grafn[nod][i]);
st[k]=nod;
k++;
}
void dftrans(int nod)
{
viz[nod]=0;
con[k].push_back(nod);
for(int i=0;i<graftrans[nod].size();i++)
if(viz[graftrans[nod][i]]) dftrans(graftrans[nod][i]);
}
int main()
{
f>>n>>m;
for(int i=1;i<=m;i++)
{
int a,b;
f>>a>>b;
grafn[a].push_back(b);
graftrans[b].push_back(a);
}
for(int i=1;i<=n;i++)
if(!viz[i]) dfnormal(i);
k=0;
for(int i=n-1;i>=0;i--)
if(viz[st[i]])
{
dftrans(st[i]);
k++;
}
g<<k<<"\n";
for(int i=0;i<k;i++)
{
for(int j=0;j<con[i].size();j++)
g<<con[i][j]<<" ";
g<<"\n";
}
return 0;
}