Pagini recente » Cod sursa (job #847191) | Cod sursa (job #1536281) | Cod sursa (job #1540378) | Cod sursa (job #2983036) | Cod sursa (job #2464593)
#include<iostream>
#include<vector>
#include<stack>
using namespace std;
const int N = 1e5 + 10;
const int M = 2e5 + 10;
vector<int> nbrs[N];
int br = 0;
int index[N];
int lowLink[N];
stack<int> st;
bool inStack[N];
int compCount = 0;
vector<int> output;
void dfs(int currentV)
{
index[currentV] = br;
lowLink[currentV] = br;
++br;
st.push(currentV);
inStack[currentV] = true;
for(int i = 0; i < nbrs[currentV].size(); ++i)
{
int nextV = nbrs[currentV][i];
if(index[nextV] == -1)
{
dfs(nextV);
lowLink[currentV] =
min(lowLink[currentV], lowLink[nextV]);
}
else if(inStack[nextV])
{
/// TODO: check if lowLink works the same
lowLink[currentV] =
min(lowLink[currentV], index[nextV]);
}
}
if(index[currentV] == lowLink[currentV])
{
//cout << "New SCC:\n";
while(st.top() != currentV)
{
output.push_back(st.top() + 1);
//cout << st.top() + 1 << " ";
st.pop();
}
output.push_back(st.top() + 1);
output.push_back(-1);
//cout << st.top() + 1 << endl;
st.pop();
++compCount;
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int n;
int m;
cin >> n >> m;
for(int i = 0; i < m; ++i)
{
int from, to;
cin >> from >> to;
--from;
--to;
nbrs[from].push_back(to);
}
for(int i = 0; i < n; ++i)
{
index[i] = -1;
lowLink[i] = -1;
}
for(int i = 0; i < n; ++i)
{
if(index[i] == -1)
{
dfs(i);
}
}
cout << compCount << endl;
for(int i = 0; i < output.size(); ++i)
{
if(output[i] == -1)
{
cout << endl;
}
else
{
cout << output[i] << " ";
}
}
return 0;
}