Pagini recente » Cod sursa (job #706764) | Cod sursa (job #2089932) | Cod sursa (job #893224) | Cod sursa (job #2885320) | Cod sursa (job #629799)
Cod sursa(job #629799)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int MAXN = 100002;
int N , M , x , y , indecs , scnt;
vector< vector<int> > C;
vector<int> G[MAXN] , con , pre , id;
stack<int> S , P;
void read_data()
{
for(fin>>N>>M;M;M--)
fin>>x>>y ,
G[x].push_back(y);
pre.resize(N+1,-1) , id.resize(N+1,-1);
}
void gabow(const int node)
{
pre[node] = indecs++;
S.push(node) , P.push(node);
for(vector<int>::const_iterator it=G[node].begin();it!=G[node].end();++it)
if(pre[*it]==-1) gabow(*it);
else
if (id[*it]) while(pre[P.top()]>pre[*it]) P.pop();
if(P.top() == node)
{
P.pop(); int currnod;
con.clear();
do{
con.push_back( currnod = S.top());
S.pop() , id[currnod] = scnt;
} while(currnod!=node);
C.push_back(con);
}
}
int main()
{
read_data();
for(int i=1;i<=N;++i)
if(pre[i]==-1) gabow(i);
fout<<C.size()<<'\n';
for(int i=0;i<(int)C.size();++i)
{
for(int j=0;j<(int)C[i].size();++j)
fout<<C[i][j]<<' ';
fout<<'\n';
}
return 0;
}