Pagini recente » Cod sursa (job #1808042) | Cod sursa (job #2587887) | Cod sursa (job #1234611) | Cod sursa (job #2658798) | Cod sursa (job #3341517)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream be("ctc.in");
ofstream ki("ctc.out");
struct vertices
{
int index, lowlink;
bool onstack;
vertices()
{
index = -1;
lowlink = 0;
onstack = false;
}
};
void tarjan(int v, int &index, stack<int> &s, vector<vertices> &V, vector<vector<int>> &E, vector<vector<int>> &ans)
{
V[v].index = index;
V[v].lowlink = index;
index++;
s.push(v);
V[v].onstack = true;
for(int w : E[v])
{
if(V[w].index == -1)
{
tarjan(w, index, s, V, E, ans);
V[v].lowlink = min(V[v].lowlink, V[w].lowlink);
}else if(V[w].onstack)
{
V[v].lowlink = min(V[v].lowlink, V[w].index);
}
}
if(V[v].lowlink == V[v].index)
{
vector<int> component;
int w;
do
{
w = s.top();
s.pop();
V[w].onstack = false;
component.push_back(w);
}while(v != w);
ans.push_back(component);
}
}
int main()
{
int n, m;
be >> n >> m;
vector<vector<int>> E(n + 1);
for(int i = 0; i < m; i++)
{
int u, v;
be >> u >> v;
E[u].push_back(v);
}
vector<vertices> V(n + 1);
stack<int> s;
vector<vector<int>> ans;
int index = 0;
for(int i = 1; i <= n; i++)
{
if(V[i].index == -1)
{
tarjan(i, index, s, V, E, ans);
}
}
int size = (int)ans.size();
ki << size << "\n";
for(int i = 0; i < size; i++)
{
for(int j : ans[i])
{
ki << j << " ";
}
ki << "\n";
}
return 0;
}