Pagini recente » Cod sursa (job #2758589) | Cod sursa (job #253425) | Cod sursa (job #2737302) | Cod sursa (job #2537484) | Cod sursa (job #749709)
Cod sursa(job #749709)
#include <stack>
#include <vector>
#include <fstream>
#include <cstdlib>
#include <iterator>
#include <algorithm>
using namespace std;
const int N_MAX=100011;
int idx, ctcSize;
bool was[N_MAX], isInStack[N_MAX];
int dfsIDX[N_MAX], lowIDX[N_MAX];
stack<int> S;
vector<int> G[N_MAX], CTC[N_MAX];
vector<int>::const_iterator it, iend;
inline void DFS(int x)
{
S.push(x);
was[x]=true;
isInStack[x]=true;
lowIDX[x]=dfsIDX[x]=++idx;
vector<int>::const_iterator it=G[x].begin(), iend=G[x].end();
for(; it < iend; ++it)
{
if(false == was[*it])
{
DFS(*it);
if(lowIDX[*it] < lowIDX[x])
lowIDX[x]=lowIDX[*it];
}
else if(true == isInStack[*it] && lowIDX[*it] < lowIDX[x])
lowIDX[x]=lowIDX[*it];
}
if(lowIDX[x] == dfsIDX[x])
{
int y;
do {
y=S.top(); S.pop();
isInStack[y]=false;
CTC[ctcSize].push_back(y);
}while(y != x);
++ctcSize;
}
}
int main()
{
int N, M, x, y;
ifstream in("ctc.in");
ofstream out("ctc.out");
for(in>>N>>M; M; --M)
{
in>>x>>y;
G[x].push_back(y);
}
for(x=1; x <= N; ++x)
if(false == was[x])
DFS(x);
out<<ctcSize<<'\n';
for(x=0; x < ctcSize; ++x)
{
for(it=CTC[x].begin(), iend=CTC[x].end(); it < iend; ++it)
out<<*it<<' ';
out<<'\n';
}
return EXIT_SUCCESS;
}