Pagini recente » Cod sursa (job #874348) | Cod sursa (job #874208) | Cod sursa (job #1371926) | Cod sursa (job #2483328) | Cod sursa (job #1132413)
#include <fstream>
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
#define no_nodes 100001
vector <int> my_nodes[no_nodes], scc[no_nodes];
stack <int> my_stack;
int bStack[no_nodes], index[no_nodes], LowLink[no_nodes], n, m, no_scc = 0, Index = 0;
void Tarjan(int t)
{
index[t] = Index;
LowLink[t] = Index;
Index ++;
my_stack.push(t);
bStack[t] = 1;
for (int i = 0; i < my_nodes[t].size(); i ++)
if (index[my_nodes[t][i]] == -1)
{
Tarjan(my_nodes[t][i]);
LowLink[t] = min(LowLink[t], LowLink[my_nodes[t][i]]);
}
else
if (bStack[my_nodes[t][i]])
LowLink[t] = min(LowLink[t], index[my_nodes[t][i]]);
if (LowLink[t] == index[t])
{
int temp;
do
{
temp = my_stack.top();
bStack[temp] = 0;
scc[no_scc].push_back(temp);
my_stack.pop();
}
while (temp != t);
no_scc ++;
}
}
int main()
{
int t1, t2;
ifstream f("ctc.in");
ofstream g("ctc.out");
f >> n >> m;
for (int i = 1; i <= m; i ++)
{
f >> t1 >> t2;
my_nodes[t1].push_back(t2);
}
for (int i = 1; i <= n; i ++)
{
bStack[i] = 0;
index[i] = -1;
}
for (int i = 1; i <= n; i ++)
if (index[i] == -1)
Tarjan(i);
g << no_scc << '\n';
for (int i = 0; i < no_scc; i ++)
{
for (int j = 0; j < scc[i].size(); j++)
g << scc[i][j] << " ";
g << '\n';
}
f.close();
g.close();
return 0;
}