Pagini recente » Cod sursa (job #822701) | Cod sursa (job #989319) | Cod sursa (job #2263563) | Cod sursa (job #2535480) | Cod sursa (job #787479)
Cod sursa(job #787479)
#include <fstream>
#include <vector>
#include <stack>
#define NM 100010
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int N,M,i,j;
int K;
int a,b;
vector<int> G[NM];
vector<int> ANS[NM];
stack<int> S;
int NCTC;
int Lev[NM],MinLev[NM];
bool InS[NM];
void DoTarjan (int nod)
{
Lev[nod]=MinLev[nod]=++K;
S.push(nod);
InS[nod]=1;
int nnod;
for (vector<int>::iterator it=G[nod].begin(); it!=G[nod].end(); it++)
{
nnod=*it;
if (!Lev[nnod])
{
DoTarjan(nnod);
MinLev[nod]=min(MinLev[nod],MinLev[nnod]);
continue;
}
if (InS[nnod])
MinLev[nod]=min(MinLev[nod],MinLev[nnod]);
}
if (Lev[nod]==MinLev[nod])
{
++NCTC;
while (!S.empty() && S.top()!=nod)
{
InS[S.top()]=0;
ANS[NCTC].push_back(S.top());
S.pop();
}
if (!S.empty())
{
InS[S.top()]=0;
ANS[NCTC].push_back(S.top());
S.pop();
}
}
}
int main ()
{
f >> N >> M;
for (i=1; i<=M; i++)
{
f >> a >> b;
G[a].push_back(b);
}
for (i=1; i<=N; i++)
if (!Lev[i])
DoTarjan(i);
g << NCTC << '\n';
for (i=1; i<=NCTC; i++)
{
for (j=0; j<ANS[i].size(); j++)
g << ANS[i][j] << ' ';
g << '\n';
}
f.close();
g.close();
return 0;
}