Pagini recente » Cod sursa (job #1361500) | Cod sursa (job #2508264) | Cod sursa (job #2654473) | Cod sursa (job #3279797) | Cod sursa (job #1254478)
#include <fstream>
#include <vector>
#include <bitset>
#include <stack>
using namespace std;
#define SZ 100003
#define INF 1<<27
ifstream is ("ctc.in");
ofstream os ("ctc.out");
int N, M, Index[SZ], L[SZ], idx;
bitset<SZ> B;
vector <int> G[SZ], C;
vector < vector <int> > SCC;
stack <int> S;
void Tarjan(int x);
int main()
{
is >> N >> M;
for (int i = 1; i <= N; ++i)
Index[i] = INF;
for (int i = 1, a, b; i <= M; ++i)
{
is >> a >> b;
G[a].push_back(b);
}
for (int i = 1; i <= N; ++i)
if (Index[i] == INF)
Tarjan(i);
os << SCC.size() << '\n';
for (int i = 0; i < SCC.size(); ++i)
{
for (int j = 0; j < SCC[i].size(); ++j)
os << SCC[i][j] << ' ';
os << '\n';
}
is.close();
os.close();
}
void Tarjan(int x)
{
Index[x] = L[x] = idx++;
S.push(x);
B[x] = 1;
int node;
for (int j = 0; j < G[x].size(); ++j)
{
node = G[x][j];
if (Index[node] == INF)
{
Tarjan(node);
L[x] = min(L[x], L[node]);
}
else
if (B[node] == 1)
L[x] = min(L[x], L[node]);
}
if (L[x] == Index[x])
{
do
{
node = S.top(), S.pop();
C.push_back(node);
B[node] = 0;
}
while (node != x);
SCC.push_back(C);
C.clear();
}
};