Pagini recente » Cod sursa (job #1311844) | Monitorul de evaluare | Cod sursa (job #2314739) | Cod sursa (job #1165552) | Cod sursa (job #755771)
Cod sursa(job #755771)
#include <stack>
#include <vector>
#include <fstream>
#include <cstdlib>
#include <iterator>
#include <algorithm>
using namespace std;
const int N_MAX=100011;
stack<int> S;
vector<int> G[N_MAX], CTC[N_MAX];
int index, ctcSize;
bool isInStack[N_MAX];
int lowIndex[N_MAX], dfsIndex[N_MAX];
inline int _min(int x, int y) {return x <= y ? x : y;}
inline void DFS(int x)
{
S.push(x);
isInStack[x]=true;
lowIndex[x]=dfsIndex[x]=++index;
vector<int>::const_iterator it=G[x].begin(), iend=G[x].end();
for(; it < iend; ++it)
if(0 == dfsIndex[*it])
{
DFS(*it);
lowIndex[x]=_min(lowIndex[x], lowIndex[*it]);
}
else if(true == isInStack[*it] && lowIndex[x] > lowIndex[*it])
lowIndex[x]=lowIndex[*it];
if(dfsIndex[x] == lowIndex[x])
{
static int y;
do {
y=S.top(); S.pop();
isInStack[y]=false;
CTC[ctcSize].push_back(y);
}while(x != y);
++ctcSize;
}
}
int main()
{
int N, M, x, y, i;
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(0 == dfsIndex[x])
DFS(x);
out<<ctcSize<<'\n';
for(i=0; i < ctcSize; ++i)
{
copy(CTC[i].begin(), CTC[i].end(), ostream_iterator<int>(out, " "));
out<<'\n';
}
return EXIT_SUCCESS;
}