Pagini recente » Cod sursa (job #1863688) | Borderou de evaluare (job #1330358) | Cod sursa (job #3254905) | Clasamentul arhivei educationale | Cod sursa (job #727017)
Cod sursa(job #727017)
#include<fstream>
#include<sstream>
#include<stack>
#include<vector>
#define _NM 100010
using namespace std;
bool viz[_NM];
void dfs(vector<int> vAd[], int nod, stack<int> &enu)
{
if (viz[nod]) return;
viz[nod]=1;
for (vector<int>::iterator it=vAd[nod].begin();it!=vAd[nod].end();++it)
dfs(vAd,*it,enu);
enu.push(nod);
}
int main()
{
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int nN, nM;
fin>>nN>>nM;
static vector<int> vAd[_NM], vAd_t[_NM];
for (int i=1;i<=nM;i++)
{
int nod1, nod2;
fin>>nod1>>nod2;
vAd[nod1].push_back(nod2);
vAd_t[nod2].push_back(nod1);
}
stack<int> order;
for (int i=1;i<=nN;i++)
dfs(vAd,i,order);
//global viz
for (int i=1;i<=nN;i++) viz[i]=0;
stringstream ss; int sol_cnt=0;
while (!order.empty())
{
stack<int> sol;
dfs(vAd_t,order.top(),sol);
order.pop();
if (!sol.empty())
{
sol_cnt++;
while (!sol.empty())
{
ss<<sol.top()<<' ';
sol.pop();
}
ss<<'\n';
}
}
fout<<sol_cnt<<'\n'<<ss.str();
return 0;
}