Pagini recente » Cod sursa (job #206348) | Cod sursa (job #2803982) | Cod sursa (job #1231236) | Cod sursa (job #2889507) | Cod sursa (job #2659806)
#include <iostream>
#include <fstream>
#include <list>
#include <stack>
#include <vector>
std::ifstream in("ctc.in");
std::ofstream out("ctc.out");
class Graf
{
int n,size;
std::list<int>* g;
std::list<int> *ad;
void SCCUtil(int u, int disc[], int low[],
std::stack<int> *st, bool stackMember[]);
public:
Graf(int n);
void addEdge(int i, int j);
void SCC();
};
Graf::Graf(int n)
{
this->n = n;
ad = new std::list<int>[n+1];
g = new std::list<int> [n+1];
size = 0;
}
void Graf::addEdge(int i, int j)
{
ad[i].push_back(j);
}
void Graf::SCCUtil(int u, int disc[], int low[], std::stack<int> *st,
bool stackMember[])
{
static int time = 0;
disc[u] = low[u] = ++time;
st->push(u);
stackMember[u] = true;
std::list<int>::iterator i;
for (i = ad[u].begin(); i != ad[u].end(); ++i)
{
int v = *i;
if (disc[v] == -1)
{
SCCUtil(v, disc, low, st, stackMember);
low[u] = std::min(low[u], low[v]);
}
else if (stackMember[v] == true)
low[u] = std::min(low[u], disc[v]);
}
int w = 0;
if (low[u] == disc[u])
{
size ++;
while (st->top() != u)
{
w = (int) st->top();
g[size].push_back(w);
stackMember[w] = false;
st->pop();
}
w = (int) st->top();
g[size].push_back(w);
stackMember[w] = false;
st->pop();
}
}
void Graf::SCC()
{
int *disc = new int[n];
int *low = new int[n];
bool *stackMember = new bool[n];
std::stack<int> *st = new std::stack<int>();
for (int i = 1; i <= n; i++)
{
disc[i] = -1;
low[i] = -1;
stackMember[i] = false;
}
for (int i = 1; i <= n; i++)
if (disc[i] == -1)
SCCUtil(i, disc, low, st, stackMember);
out << size << "\n";
while (size){
std::list<int>::iterator i;
for (i = g[size].begin(); i != g[size].end(); i ++)
out << *i << " ";
out << "\n";
size--;
}
}
int main()
{
int n,m;
in >> n >> m;
Graf graf(n);
while (m){
int i, j;
in >> i >> j;
graf.addEdge(i,j);
m --;
}
graf.SCC();
out.close();
in.close();
return 0;
}