Pagini recente » Cod sursa (job #2285125) | Cod sursa (job #402638) | Cod sursa (job #663040) | Cod sursa (job #1922700) | Cod sursa (job #1327722)
#include <fstream>
#include <vector>
#include <bitset>
#include <stack>
using namespace std;
#define NSIZE 100003
#define INF 1<<27
ifstream is ("ctc.in");
ofstream os ("ctc.out");
int N, M, Index[NSIZE], L[NSIZE], idx;
bool B[NSIZE];
vector <int> G[NSIZE], C;
vector < vector <int> > SCC;
stack <int> S;
void Tarjan(int x);
int main()
{
is >> N >> M;
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] == 0)
Tarjan(i);
os << SCC.size() << '\n';
for (int i = 0; i < SCC.size(); ++i, os << '\n')
for (const int& j : SCC[i])
os << j << ' ';
is.close();
os.close();
}
void Tarjan(int x)
{
Index[x] = L[x] = ++idx;
S.push(x), B[x] = 1;
for (const int& i : G[x])
if (Index[i] == 0)
{
Tarjan(i);
L[x] = min(L[x], L[i]);
}
else
if (B[i] == 1)
L[x] = min(L[x], L[i]);
if (Index[x] == L[x])
{
C.clear();
int node;
do
{
node = S.top(); S.pop();
C.push_back(node); B[node] = 0;
}
while (!S.empty() && node != x);
SCC.push_back(C);
C.clear();
}
};