Pagini recente » Cod sursa (job #2761109) | Cod sursa (job #719967) | Cod sursa (job #228853) | Cod sursa (job #2185894) | Cod sursa (job #1491006)
#include <fstream>
#include <string.h>
#include <algorithm>
#include <bitset>
using namespace std;
const int Nmax = 100000;
const int Mmax = 200000;
const int NIL = -1;
struct cell
{
int v, next;
};
cell l[Mmax];
int adj[Nmax];
int indx[Nmax], lowLink[Nmax], ptr;
bitset <Nmax> onStack;
int stack[Nmax], s;
cell sccBuff[Nmax];
int sccPtr;
int scc[Nmax], sccCount;
void addEdge(int u, int v, int pos)
{
l[pos].v = v;
l[pos].next = adj[u];
adj[u] = pos;
}
void dfs(int node)
{
indx[node] = lowLink[node] = ++ptr;
stack[s++] = node;
onStack[node] = 1;
for (int i = adj[node]; ~i; i = l[i].next)
{
int son = l[i].v;
if (!indx[son])
{
dfs(son);
lowLink[node] = min(lowLink[node], lowLink[son]);
}
else if (onStack[son])
lowLink[node] = min(lowLink[node], lowLink[son]);
}
if (indx[node] == lowLink[node])
{
int v;
do
{
v = stack[--s];
onStack[v] = 0;
sccBuff[sccPtr].v = v;
sccBuff[sccPtr].next = scc[sccCount];
scc[sccCount] = sccPtr++;
} while (v != node);
sccCount++;
}
}
int main()
{
ifstream in("ctc.in");
ofstream out("ctc.out");
in.tie(0);
ios_base::sync_with_stdio(0);
int n, m;
int u, v;
in >> n >> m;
memset(adj, NIL, sizeof(adj));
memset(scc, NIL, sizeof(scc));
for (int i = 0; i < m; i++)
{
in >> u >> v;
addEdge(u - 1, v - 1, i);
}
in.close();
for (int i = 0; i < n; i++)
{
if (!indx[i])
dfs(i);
}
out << sccCount << '\n';
for (int i = 0; i < sccCount; i++)
{
for (int j = scc[i]; ~j; j = sccBuff[j].next)
out << sccBuff[j].v + 1 << ' ';
out << '\n';
}
out.close();
return 0;
}