Pagini recente » Cod sursa (job #165999) | Cod sursa (job #280344) | Cod sursa (job #51202) | Cod sursa (job #2710268) | Cod sursa (job #964601)
Cod sursa(job #964601)
/*
3.0 featuring TARJAN
*/
#include <fstream>
#include <vector>
#include <bitset>
#include <queue>
#include <algorithm>
#include <ctime>
#include <utility>
#include <stack>
#include <set>
using namespace std;
const int NMAX = 100005;
ofstream cout("ctc.out");
vector <int> G[NMAX], idx(NMAX, -1), lowlink(NMAX), con;
vector< vector<int> > C;
bitset <NMAX> in_Stack;
stack <int> Stack;
int n , m, indecs;
void read();
void tarjan(int);
void write();
inline int min(int a, int b)
{
if( a > b)
return b;
return a;
}
int main()
{
read();
for(int i = 1 ; i <= n ; ++ i)
if(idx[i] == -1)
tarjan(i);
write();
return 0;
}
void read()
{
ifstream cin("ctc.in");
cin >> n >> m;
for(int i = 1 ; i <= m ; ++ i)
{
int x, y;
cin >> x >> y;
G[x].push_back(y);
}
}
void tarjan(int node)
{
idx[node] = lowlink[node] = ++indecs;
Stack.push(node);
in_Stack[node] = true;
for(vector<int> :: iterator it = G[node].begin(); it != G[node].end() ; ++ it)
if(idx[*it] == -1)
{
tarjan(*it);
lowlink[node] = min(lowlink[node] , lowlink[*it]);
}
else if(in_Stack[*it])
lowlink[node] = min(lowlink[node] , lowlink[*it]);
if(idx[node] == lowlink[node])
{
con.clear();
int nod;
do
{
con.push_back(nod = Stack.top()); //initialize
Stack.pop(); in_Stack[nod] = false;
} while(nod != node);
C.push_back(con);
}
}
void write()
{
cout << C.size() << "\n";
for(vector< vector<int> > :: iterator it = C.begin(); it != C.end(); ++ it)
{
//cout << it->size() << " ";
for( vector<int> :: iterator it2 = it->begin(); it2 != it->end(); ++ it2)
cout << *it2 << " " ;
cout << "\n";
}
}