Pagini recente » Cod sursa (job #1971912) | Cod sursa (job #2775410) | Cod sursa (job #44261) | Cod sursa (job #1518070) | Cod sursa (job #2923797)
#include <fstream>
#include <vector>
using namespace std;
ifstream in ("ctc.in");
ofstream out ("ctc.out");
const int N=1e5 +5;
const int M=2e5 +5;
const int inf=1e9;
int index1[N];
int indexcur;
int indexmax[N];
bool instiva[N];
bool procesat[N];
vector <int> v[N];
int n,m;
vector <int> tc[N];
int compcur;
vector <int> stiva;
void f1(int nod)
{
if (!instiva[nod] && !procesat[nod]){
stiva.push_back(nod);
instiva[nod]=1;
procesat[nod]=1;
index1[nod]=indexcur;
indexcur++;
indexmax[nod]=index1[nod];
for (int i=0;i<v[nod].size();i++){
f1(v[nod][i]);
if (instiva[v[nod][i]] && indexmax[v[nod][i]]<indexmax[nod]){
indexmax[nod]=indexmax[v[nod][i]];
}
}
if (index1[nod]==indexmax[nod]){
while(stiva.back()!=nod){
tc[compcur].push_back(stiva.back());
stiva.pop_back();
instiva[stiva.back()]=0;
}
stiva.pop_back();
tc[compcur].push_back(nod);
instiva[nod]=0;
compcur++;
}
}
}
int main()
{
in>>n>>m;
for (int i=0;i<m;i++){
int x,y;
in>>x>>y;
v[x].push_back(y);
}
f1(1);
out<<compcur<<"\n";
for (int i=0;i<compcur;i++){
for (int j=0;j<tc[i].size();j++){
out<<tc[i][j]<<" ";
}
out<<"\n";
}
return 0;
}