Pagini recente » Cod sursa (job #1648481) | Cod sursa (job #2817831) | Cod sursa (job #1715460) | Cod sursa (job #1734129) | Cod sursa (job #1283299)
#include <fstream>
#include <stack>
#include <list>
#include <queue>
using namespace std;
list<int> adiacList[100001];
int index[100001], idx;
int lowlink[100001];
int convCounter;
short isInStack[100001];
queue<int> printQue;
stack<int> st;
void tarjan(int x)
{
index[x] = idx;
lowlink[x] = idx++;
st.push(x);
isInStack[x] = 1;
list<int>::iterator it, it_end = adiacList[x].end();
for (it = adiacList[x].begin(); it != it_end; ++it)
{
if (!index[*it])
{
tarjan(*it);
lowlink[x] = (lowlink[x] < lowlink[*it]) ? lowlink[x] : lowlink[*it];
}
else if (isInStack[*it])
{
lowlink[x] = (lowlink[x] < index[*it]) ? lowlink[x] : index[*it];
}
}
int y;
if (index[x] == lowlink[x])
{
do
{
y = st.top();
st.pop();
isInStack[y] = 0;
printQue.push(y);
}
while (y != x);
printQue.push(0);
++convCounter;
}
}
int main()
{
FILE * fin = fopen("ctc.in", "r");
FILE * fout = fopen("ctc.out", "w");
int n, m, i, j;
fscanf(fin, "%d %d", &n, &m);
while (m--)
{
fscanf(fin, "%d %d", &i, &j);
adiacList[i].push_back(j);
//adiacList[j].push_back(i);
}
for (i = 1; i <= n; ++i)
{
if (!index[i])
tarjan(i);
}
fprintf(fout, "%d\n", convCounter);
while (!printQue.empty())
{
i = printQue.front();
printQue.pop();
if (i)
fprintf(fout, "%d ", i);
else
fprintf(fout, "\n");
}
fclose(fin);
fclose(fout);
return 0;
}