Pagini recente » Cod sursa (job #1527853) | Cod sursa (job #570433)
Cod sursa(job #570433)
#include<fstream>
#include<stack>
#include<vector>
#include<iostream>
#define infile "ctc.in"
#define outfile "ctc.out"
void ctc (std::stack<int> &s,
std::vector<std::vector<int> >& vec,
std::vector<std::pair<int,int> >& atribut,
int nod,
std::vector<std::vector<int> >& sol)
{
static int timp = 0;
atribut[nod].first = atribut[nod].second = timp;
++ timp;
s.push(nod);
std::vector<int>::iterator it;
for(it = vec[nod].begin(); it != vec[nod].end(); ++it){
if(atribut[*it].first == -1){
ctc(s,vec,atribut,*it,sol);
if(atribut[nod].second > atribut[*it].second)
atribut[nod].second = atribut[*it].second;
}
else if(atribut[*it].first >= 0){
if(atribut[*it].second < atribut[nod].second)
atribut[nod].second = atribut[*it].second;
}
}
if(atribut[nod].first == atribut[nod].second){
std::vector<int> comp;
int w;
do{
w = s.top();
s.pop();
comp.push_back(w);
atribut[w].first = -2;
}while(w!=nod);
sol.push_back(comp);
}
}
int main()
{
int n, m, i;
std::stack<int> s;
std::ifstream fin(infile);
std::ofstream fout(outfile);
fin >> n >> m;
std::vector<std::vector<int> >vec;
std::vector<std::pair<int,int> >atribut;
std::vector<std::vector<int> > sol;
for(i = 0; i<n; ++i){
atribut.push_back(std::pair<int,int>(-1,-1));
std::vector<int> v;
vec.push_back(v);
}
for(i = 0; i<m; ++i){
int x,y;
fin >> x >> y;
vec[x-1].push_back(y-1);
}
for(i = 0; i<n; ++i)
if(atribut[i].first == -1)
ctc(s,vec,atribut,i,sol);
fout<<sol.size()<<std::endl;
for(i = 0; i<sol.size(); ++i){
int j;
for(j = 0; j<sol[i].size(); ++j)
fout<<sol[i][j] + 1<<" ";
fout<<std::endl;
}
fin.close();
fout.close();
return 0;
}