Pagini recente » Istoria paginii runda/simulare_oji_01/clasament | Cod sursa (job #1771274) | Istoria paginii runda/test_unu/clasament | Istoria paginii runda/test_durata | Cod sursa (job #2928466)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector <int> *laG, *laGt, *rez;
stack <int> S;
void DFSG(int s, int viz[])
{
viz[s]=1;
for (int i=0; i<laG[s].size(); i++)
{
int y=laG[s][i];
if(viz[y]==0)
DFSG(y, viz);
}
S.push(s);
}
void DFSGt(int s, int viz[], int cnt)
{
viz[s]=1;
rez[cnt].push_back(s);
for (int i=0; i<laGt[s].size(); i++)
{
int y=laGt[s][i];
if(viz[y]==0)
DFSGt(y, viz, cnt);
}
}
int main()
{
int n, m, x, y, cnt=0;
fin>>n>>m;
laG= new vector<int> [n+1];
laGt= new vector<int> [n+1];
rez= new vector<int> [n+1];
int c=m;
while (c>0)
{
fin>>x>>y;
laG[x].push_back(y);
laGt[y].push_back(x);
c--;
}
/*
for(x=0; x<n; x++)
{
cout<<x<<": ";
for (int i=0; i<la[x].size(); i++)
cout<<la[x][i]<<" ";
cout<<endl;
}
*/
int viz1[n+1]= {};
for (int i=0; i<n; i++)
if(viz1[i]==0)
DFSG(i, viz1);
int viz2[n+1]= {};
while(!S.empty())
{
int q=S.top();
S.pop();
if(viz2[q]==0)
{
DFSGt(q, viz2, cnt);
cnt++;
}
}
cnt--;
fout<<cnt<<endl;
for (int i=0; i<cnt; i++)
{
for (int j=0; j<rez[i].size(); j++)
fout<<rez[i][j]<<" ";
fout<<endl;
}
return 0;
}