Pagini recente » Cod sursa (job #2627826) | Cod sursa (job #170454) | Cod sursa (job #1816836) | Cod sursa (job #344310) | Cod sursa (job #1719918)
#include <iostream>
#include <fstream>
#include <cstdio>
#include <vector>
#include <stack>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
vector<vector<int> > graf;
struct Node
{
int lowlink;
int discover;
int inStack;
};
vector<Node> nodes;
stack<int> s;
vector<vector<int> > comps;
int nrcomps;
int timp;
void tarjan(int i)
{
nodes[i].discover = timp;
nodes[i].lowlink = timp;
timp++;
s.push(i);
nodes[i].inStack = 1;
for (int k = 0; k < graf[i].size(); k++)
{
int neighbour = graf[i][k];
if (nodes[neighbour].discover == -1)
{
tarjan(neighbour);
nodes[i].lowlink = min(nodes[i].lowlink, nodes[neighbour].lowlink);
}
else
{
if (nodes[neighbour].inStack)
//backedge
nodes[i].lowlink = min(nodes[i].lowlink, nodes[neighbour].discover);
}
}
if (nodes[i].lowlink == nodes[i].discover)
{
int u;
do
{
u = s.top();
s.pop();
nodes[u].inStack = 0;
comps[nrcomps].push_back(u);
} while (u != i);
nrcomps++;
}
}
void getComponents()
{
for (int i = 0; i < nodes.size(); i++)
{
nodes[i].discover = -1;
nodes[i].inStack = 0;
}
for (int i = 1; i < nodes.size(); i++)
{
if (nodes[i].discover == -1)
{
tarjan(i);
}
}
}
void print()
{
out << nrcomps << "\n";
for (int i = 0; i < nrcomps; i++)
{
for (int j = 0; j < comps[i].size(); j++)
out << comps[i][j] << " ";
out << "\n";
}
}
int main()
{
int n, m;
in >> n >> m;
graf.resize(n+1);
nodes.resize(n+1);
comps.resize(n+1);
nrcomps = 0;
timp = 0;
for (int i = 0; i < m; i++)
{
int x,y;
in >> x >> y;
graf[x].push_back(y);
}
getComponents();
print();
}