Pagini recente » Cod sursa (job #3127701) | Cod sursa (job #190360) | Cod sursa (job #2369494) | Cod sursa (job #291797) | Cod sursa (job #780750)
Cod sursa(job #780750)
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
#define nmax 100010
int index[nmax], lowLink[nmax], N, M, X, Y, number = 1;
bool InStack[nmax];
stack<int> S;
vector<int> G[nmax];
vector<vector<int> > ctc;
void Tarjan(int startNode);
int main()
{
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
int i, j;
scanf("%i %i", &N, &M);
for(i = 1; i <= M; i++)
{
scanf("%i %i", &X, &Y);
G[Y].push_back(X);
}
for(i = 1; i <= N; i++)
if(index[i] == 0)
Tarjan(i);
printf("%i\n", ctc.size());
for(i = 0; i < ctc.size(); i++)
{
for(j = 0; j < ctc[i].size(); j++) printf("%i ", ctc[i][j]);
printf("\n");
}
return 0;
}
void Tarjan(int startNode)
{
index[startNode] = lowLink[startNode] = number ++;
S.push(startNode);
InStack[startNode] = true;
for(vector<int> :: iterator it = G[startNode].begin(); it != G[startNode].end(); ++it)
{
if(index[*it] == 0)
{
Tarjan(*it);
lowLink[startNode] = min(lowLink[startNode], lowLink[*it]);
}else
{
if(InStack[*it])
{
lowLink[startNode] = min(lowLink[startNode], index[*it]);
}
}
}
if(lowLink[startNode] == index[startNode])
{
vector<int> New;
int node = 0;
while(node != startNode)
{
node = S.top();
S.pop();
New.push_back(node);
InStack[node] = false;
}
ctc.push_back(New);
}
}