Pagini recente » Cod sursa (job #1690918) | Cod sursa (job #2070936) | Statistici Boiculese Claudiu (yusty95sv) | Cod sursa (job #1077098) | Cod sursa (job #973326)
Cod sursa(job #973326)
#include <fstream>
#include <vector>
#include <bitset>
#include <queue>
#include <algorithm>
#include <utility>
#include <string.h>
#include <set>
#include <stack>
#define add push_back
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
const int MAXN = 100005;
const int oo = (1<<31)-1;
typedef vector<int> Graph[MAXN];
typedef vector<int> :: iterator It;
Graph G;
int N, M, deep;
vector<int> Lowlink(MAXN), Deep(MAXN);
stack<int> Stack;
set< set<int> > StronglyConnectedComponents;
bitset<MAXN> in_Stack;
inline void Get_min(int &a, int b){
if(a>b)
a=b;
}
void ReadData(){
cin >> N >> M;
for(int i = 1 ; i <= M ; ++ i){
int X, Y;
cin >> X >> Y;
G[X].add(Y);
}
}
void WriteData(){
cout << StronglyConnectedComponents.size() << "\n";
for(set<set<int> > :: iterator it = StronglyConnectedComponents.begin(), fin = StronglyConnectedComponents.end() ; it != fin ; ++ it, cout << "\n")
for(set<int> :: iterator jt = it->begin() , jin = it->end() ; jt != jin ; ++ jt)
cout << *jt << " ";
}
void Tarjan(int Node){
Deep[Node] = Lowlink[Node] = ++deep;
Stack.push(Node);
in_Stack[Node] = true;
for(It it = G[Node].begin(), fin = G[Node].end() ; it != fin ; ++ it)
if(!Deep[*it]){
Tarjan(*it);
Get_min(Lowlink[Node], Lowlink[*it]);
}
else if(in_Stack[*it])
Get_min(Lowlink[Node], Lowlink[*it]);
if(Lowlink[Node] == Deep[Node]){
set<int> CurrentComponent;
int Nod;
do{
CurrentComponent.insert(Nod = Stack.top());
Stack.pop();
in_Stack[Nod] = false;
}while(Nod != Node);
StronglyConnectedComponents.insert(CurrentComponent);
}
}
void StartSolving(){
for(int i = 1 ; i <= N ; ++ i)
if(!Deep[i])
Tarjan(i);
}
int main()
{
ReadData();
StartSolving();
WriteData();
cin.close();
cout.close();
return 0;
}