Pagini recente » Cod sursa (job #1343093) | Cod sursa (job #1631139) | Cod sursa (job #2559612) | Cod sursa (job #2744188) | Cod sursa (job #2118102)
#include<fstream>
#include<list>
#include<stack>
#include<bitset>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int NMAX = 100005;
list<int> graph[NMAX], SCC[NMAX];
stack<int> Stack;
bitset<NMAX> inStack;
int nodesCount, edgesCount, traversalMoment, SCCCount;
int link[NMAX], lowLink[NMAX];
inline void read_data(){
fin >> nodesCount >> edgesCount;
int from, to;
while(edgesCount--){
fin >> from >> to;
graph[from].push_back(to);
}
}
inline void getNewSCC(int node){
++SCCCount;
int topOfTheStack;
do{
topOfTheStack = Stack.top();
inStack[topOfTheStack] = false;
Stack.pop();
SCC[SCCCount].push_back(topOfTheStack);
}while(node != topOfTheStack);
}
void getSCC(int node){
link[node] = lowLink[node] = ++traversalMoment;
Stack.push(node);
inStack[node] = true;
list<int>::iterator nextNode;
for(nextNode = graph[node].begin(); nextNode != graph[node].end(); ++nextNode)
if(link[*nextNode] == 0){
getSCC(*nextNode);
lowLink[node] = min(lowLink[node], lowLink[*nextNode]);
}
else if(inStack[*nextNode])
lowLink[node] = min(lowLink[node], lowLink[*nextNode]);
if(link[node] == lowLink[node])
getNewSCC(node);
}
inline void solve(){
int node;
for(node = 1; node <= nodesCount; ++node)
if(link[node] == 0)
getSCC(node);
}
inline void printSCC(){
fout << SCCCount << '\n';
int index;
list<int>::iterator node;
for(index = 1; index <= SCCCount; ++index){
for(node = SCC[index].begin(); node != SCC[index].end(); ++node)
fout << *node << ' ';
fout << '\n';
}
}
int main(){
read_data();
solve();
printSCC();
}