Pagini recente » Cod sursa (job #302201) | Cod sursa (job #1554610) | Cod sursa (job #2742075) | Cod sursa (job #602663) | Cod sursa (job #2118246)
#include<cstdio>
#include<list>
#include<stack>
#include<bitset>
using namespace std;
const int NMAX = 100005, BUFFERSIZE = 40000;
char readBuffer[BUFFERSIZE];
int readCursor = BUFFERSIZE - 1;
inline void read(int &number){
while(!(readBuffer[readCursor] >= '0' and readBuffer[readCursor] <= '9'))
if(++readCursor == BUFFERSIZE){
readCursor = 0;
fread(readBuffer, 1, BUFFERSIZE, stdin);
}
number = 0;
while(readBuffer[readCursor] >= '0' and readBuffer[readCursor] <= '9'){
number = number * 10 + readBuffer[readCursor] - '0';
if(++readCursor == BUFFERSIZE){
readCursor = 0;
fread(readBuffer, 1, BUFFERSIZE, stdin);
}
}
}
char printBuffer[BUFFERSIZE];
int printCursor;
inline void printChar(const char &character){
printBuffer[printCursor++] = character;
if(printCursor == BUFFERSIZE){
fwrite(printBuffer, 1, BUFFERSIZE, stdout);
printCursor = 0;
}
}
inline void printInteger(int number){
char digits[10];
int numberLength = 0;
while(number){
digits[++numberLength] = number % 10 + '0';
number /= 10;
}
while(numberLength){
printChar(digits[numberLength]);
--numberLength;
}
}
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(){
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
read(nodesCount); read(edgesCount);
int from, to;
while(edgesCount--){
read(from); read(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(){
printInteger(SCCCount);
printChar('\n');
int index;
list<int>::iterator node;
for(index = 1; index <= SCCCount; ++index){
for(node = SCC[index].begin(); node != SCC[index].end(); ++node)
printInteger(*node), printChar(' ');
printChar('\n');
}
fwrite(printBuffer, 1, BUFFERSIZE, stdout);
}
int main(){
read_data();
solve();
printSCC();
}