Pagini recente » Cod sursa (job #33807) | Cod sursa (job #2695668) | Cod sursa (job #460366) | Cod sursa (job #1094094) | Cod sursa (job #1314215)
#include <fstream>
#include <algorithm>
#include <stack>
using namespace std;
ifstream is("ctc.in");
ofstream os("ctc.out");
#define DIM 100001
struct node{
int lowlink;
int index;
};
int N, M, Index, CC, x, y;
bool B[DIM];
node D[DIM];
vector <int> G[DIM];
vector <vector <int> > Sol;
stack <int> S;
void Input();
void DFS(int);
int main()
{
Input();
for ( int i = 1; i <= N; ++i )
if ( D[i].index == 0 )
DFS(i);
os << CC << '\n';
for ( int i = 0; i < CC; ++i )
{
for ( int j = 0; j < Sol[i].size(); ++j )
os << Sol[i][j] << ' ';
os << '\n';
}
is.close();
os.close();
}
void Input()
{
is >> N >> M;
for ( int i = 1; i <= M; ++i )
{
is >> x >> y;
G[x].push_back(y);
}
}
void DFS(int x)
{
Index++;
B[x] = 1;
S.push(x);
D[x].index = Index;
D[x].lowlink = Index;
for ( const auto& v : G[x] )
{
if ( D[v].index == 0 )
{
DFS(v);
D[x].lowlink = min(D[x].lowlink,D[v].lowlink);
}
else
if ( B[v] )
D[x].lowlink = min(D[x].lowlink,D[v].index);
}
if ( D[x].lowlink == D[x].index )
{
CC++;
Sol.resize(CC);
while ( !S.empty() && S.top() != x )
{
Sol[Sol.size()-1].push_back(S.top());
B[S.top()] = 0;
S.pop();
}
Sol[Sol.size()-1].push_back(S.top());
B[S.top()] = 0;
S.pop();
}
}