Pagini recente » Cod sursa (job #782582) | Cod sursa (job #666736) | Cod sursa (job #428751) | Cod sursa (job #3219770) | Cod sursa (job #1906775)
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
struct Graf { int index, lowLink; bool inStack; vector<int> v; };
int n, index, nrComp;
Graf node[100002];
vector<int> comp[100002];
stack<int> myStack;
void GoVisit(int nod)
{
node[nod].index = ++index;
node[nod].lowLink = index;
myStack.push(nod);
node[nod].inStack = true;
for (int i = 0; i < node[nod].v.size(); i++)
{
if (!node[node[nod].v[i]].index)
{
GoVisit(node[nod].v[i]);
node[nod].lowLink = min(node[nod].lowLink, node[node[nod].v[i]].lowLink);
}
else if(node[node[nod].v[i]].inStack)
node[nod].lowLink = min(node[nod].lowLink, node[node[nod].v[i]].index);
}
if (node[nod].index == node[nod].lowLink)
{
nrComp++;
while (myStack.top() != nod)
{
comp[nrComp].push_back(myStack.top());
node[myStack.top()].inStack = false;
myStack.pop();
}
comp[nrComp].push_back(myStack.top());
myStack.pop();
}
}
int main()
{
int m, n1, n2;
fin >> n >> m;
for (int i = 1; i <= m; i++)
{
fin >> n1 >> n2;
node[n1].v.push_back(n2);
}
for (int i = 1; i <= n; i++)
if (!node[i].index)
GoVisit(i);
fout << nrComp << '\n';
for (int i = 1; i <= nrComp; i++)
{
for (int j = 0; j < comp[i].size(); j++)
fout << comp[i][j] << ' ';
fout << '\n';
}
return 0;
}