Pagini recente » Cod sursa (job #1511608) | Cod sursa (job #2813389) | Cod sursa (job #2029855) | Cod sursa (job #382229) | Cod sursa (job #2693384)
#include<fstream>
#include<list>
#include<stack>
#include<vector>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector<vector<int>> sol;
vector<int> partsol;
class graph
{
private:
int n;
list<int>* adj;
void DFS(int n, int disc[], int low[], stack<int>* st, bool instack[]);
public:
graph(int n);
void addEdge(int x, int y);
void getSCC();
};
graph::graph(int n)
{
this->n = n;
adj = new list<int>[n + 1];
}
void graph::addEdge(int x, int y)
{
adj[x].push_back(y);
}
void graph::DFS(int u, int disc[], int low[], stack<int>* st, bool instack[])
{
static int time = 0;
disc[u] = low[u] = ++time;
st->push(u);
instack[u] = true;
for (auto v : adj[u])
{
if (disc[v] == -1)
{
DFS(v, disc, low, st, instack);
low[u] = min(low[u], low[v]);
}
else
if(instack[u])
low[u] = min(low[u], disc[v]);
}
if (low[u] == disc[u])
{
partsol.clear();
int w = 0;
while (st->top() != u)
{
w = st->top();
partsol.push_back(w);
instack[w] = false;
st->pop();
}
w = st->top();
partsol.push_back(w);
instack[w] = false;
st->pop();
sol.push_back(partsol);
}
}
void graph::getSCC()
{
bool* instack = new bool[n + 1];
int* disc = new int[n + 1];
int* low = new int[n + 1];
stack<int>* st = new stack<int>();
for (int i = 1; i <= n; i++)
{
disc[i] = low[i] = -1;
instack[i] = false;
}
for (int i = 1; i <= n; i++)
if (disc[i] == -1)
DFS(i, disc, low, st, instack);
fout << sol.size() << '\n';
for (auto i : sol)
{
for (auto j : i)
fout << j << " ";
fout << '\n';
}
delete[] instack;
delete st;
delete[] disc;
delete[] low;
}
int main()
{
int n, m;
fin >> n >> m;
graph g(n);
for (int i = 1; i <= m; i++)
{
int x, y;
fin >> x >> y;
g.addEdge(x, y);
}
g.getSCC();
fin.close();
fout.close();
return 0;
}