Pagini recente » Cod sursa (job #794462) | Cod sursa (job #565293) | Cod sursa (job #3263211) | Cod sursa (job #1766407) | Cod sursa (job #519120)
Cod sursa(job #519120)
#include<fstream>
#include<vector>
#include<stack>
using namespace std;
#define NMAX 100010
const char infile[]="ctc.in";
const char outfile[]="ctc.out";
vector<int> C[NMAX];
int N,M;
vector<int> G[NMAX];
stack<int> S,P;
int order[NMAX];
bool viz[NMAX];
int contor=1;
int CTC=0;
void Gabow(int v)
{
S.push(v);
P.push(v);
order[v]=contor;
contor++;
for(unsigned int i=0;i<G[v].size();i++)
{
if(order[G[v][i]] == 0)
{
Gabow(G[v][i]);
}
else if(!viz[G[v][i]])
{
while(!P.empty() && order[P.top()] > order[G[v][i]])
{
P.pop();
}
}
}
if(P.top() == v)
{
CTC++;
while(S.top() != v)
{
C[CTC].push_back(S.top());
viz[S.top()]=1;
S.pop();
}
viz[S.top()]=1;
C[CTC].push_back(S.top());
S.pop();
P.pop();
}
}
void citire()
{
fstream fin(infile,ios::in);
fin>>N>>M;
int x,y;
for(int i=1;i<=M;i++)
{
fin>>x>>y;
G[x].push_back(y);
}
fin.close();
}
void afisare()
{
fstream fout(outfile,ios::out);
fout<<CTC<<"\n";
for(int i=1;i<=CTC;i++)
{
for(vector<int>::iterator itr=C[i].begin();itr!=C[i].end();itr++)
{
fout<<*itr<<" ";
}
fout<<"\n";
}
fout.close();
}
int main()
{
citire();
for(int i=1;i<=N;i++)
if(!order[i])
Gabow(i);
afisare();
}