Pagini recente » Cod sursa (job #167286) | Cod sursa (job #2724655) | Cod sursa (job #2623334) | Cod sursa (job #530228) | Cod sursa (job #2193626)
#include<iostream>
#include<vector>
#include<algorithm>
#include<string.h>
#include<fstream>
using namespace std;
int N, M;
vector<int> G[150010];
vector<int> G_DAG[150010];
int grade_in[150010];
int viz[150010];
int h[150010][2];
int id[150010];
int p;
int comp_conex_sz;
vector<int> stk;
vector<int> comp_conex[150010];
vector<int> rez;
ifstream in("ctc.in");
ofstream out("ctc.out");
void tarjan(int x)
{
viz[x] = 1;
h[x][0] = h[x][1] = p;
++p;
stk.push_back(x);
for (int i = 0; i < G[x].size(); ++i)
{
if (!viz[G[x][i]])
{
tarjan(G[x][i]);
h[x][1] = min(h[x][1], h[G[x][i]][1]);
}
else if(viz[G[x][i]] == 1)
{
h[x][1] = min(h[x][1], h[G[x][i]][1]);
}
}
if (h[x][0] == h[x][1])
{
++comp_conex_sz;
while (stk.back()!=x)
comp_conex[comp_conex_sz].push_back(stk.back()), viz[stk.back()] = 2, id[stk.back()] = comp_conex_sz, stk.pop_back();
stk.pop_back();
comp_conex[comp_conex_sz].push_back(x);
id[x] = comp_conex_sz;
}
}
void create_grades_dag(int x)
{
viz[x] = 1;
for (int i = 0; i < G[x].size(); ++i)
{
if (id[G[x][i]] != id[x])
{
grade_in[id[G[x][i]]]++;
G_DAG[id[x]].push_back(id[G[x][i]]);
}
if (!viz[G[x][i]])
{
create_grades_dag(G[x][i]);
}
}
}
void sort_top(int x)
{
viz[x] = 1;
for (int i = 0; i < G_DAG[x].size(); ++i)
{
if (!viz[G_DAG[x][i]])
{
sort_top(G_DAG[x][i]);
}
}
stk.push_back(x);
}
int main()
{
in >> N >> M;
for (int i = 1; i <= M;++i)
{
int x, y;
in >> x >> y;
G[x].push_back(y);
}
for (int i = 1; i <= N; ++i)
if (!viz[i])
tarjan(i);
out << comp_conex_sz << "\n";
for (int i = 1; i <= comp_conex_sz; ++i)
{
for (int j = 0; j < comp_conex[i].size(); ++j)
{
out << comp_conex[i][j] << " ";
}
out << "\n";
}
return 0;
}